← 返回 uber 的题目列表Connectivity Queries on Dynamic Components (Union-Find)
类型：online_judge
You are given n nodes labeled 1..n and a sequence of m operations. Each operation is one of:
union a b: merge the connected components containing a and b.
query x y: ask whether x and y are currently in the same connected component.
Process the operations in order and output true/false for each query.
Input
First line: n m.
Next m lines: an operation of the form union a b or query x y.
Output
For each query, print true or false on its own line.
Constraints
1 <= n <= 2e5
1 <= m <= 2e5
All node indices are within 1..n.
Examples
(see samples in Chinese version)
Example
Input
5 6
union 1 2
query 1 2
query 2 3
union 2 3
query 1 3
query 4 5
Output
true
false
true
false