5349: CF EDU - DSU - Step 1 - B. Disjoint Sets Union II
[Creator : ]
Description
Implement disjoint sets union data structure. You have to perform queries of two types:
- ${\text{union}\ u\ v}$ — unite two sets that contain $u$ and $v$, respectively;
- ${\text{get}\ v}$ — find the set to which $v$ belongs to, find the minimal and the maximal element of the set, and the total number of elements in it.
Input
The first line of the input contains two integers $n,\ m\ (1≤n,\ m≤3*10^5)$ — the number of elements and the number of queries.
Next $m$ lines contain queries, one per line. For a query union the line looks like ${union\ u\ v}$ ($1≤u,v≤n$). For a query get the line looks like ${get\ v}$ ($1≤v≤n$).
Next $m$ lines contain queries, one per line. For a query union the line looks like ${union\ u\ v}$ ($1≤u,v≤n$). For a query get the line looks like ${get\ v}$ ($1≤v≤n$).
Output
For each operation get you should output the result on a separate line in the respected order. Each result should consist of three integers: the minimal element, the maximal element and the number of elements in the set.
Sample 1 Input
5 11
union 1 2
get 3
get 2
union 2 3
get 2
union 1 3
get 5
union 4 5
get 5
union 4 1
get 5
Sample 1 Output
3 3 1
1 2 2
1 3 3
5 5 1
4 5 2
1 5 5