10302: CF EDU - DSU - Step 2 - D. Bosses
Description
There are $n$ employees in a company, and in the current moment no one is a subordinate of any other one. That is, each employee is a boss of himself. We call a person a boss, if he is not a subordinate of anybody else.
You are to process two types of queries:
- boss $a$ becomes a subordinate of boss $b$ (and no longer is a boss),
- given an employee $c$, what is the number of his superiors we should pass to reach a boss?
In a query of the second type, if $c$ is a boss, the answer is $0$, otherwise it is some positive integer — the "depth" of the employee.
Write a program that processes the queries.
Input
The first line contains two integers $n, m\ (1 ≤n,m≤ 3·10^5)$ — the number of employees and the number of queries, respectively.
The next $m$ lines contain the queries. A query of the first type is described as "1 a b" (1 ≤a≠b≤n), where a and b are bosses. A query of the second type is described as "2 c" (1 ≤c≤n).
Output
Sample 1 Input
10 20
1 9 4
1 2 6
2 10
1 10 5
2 5
1 7 4
1 8 5
2 1
1 6 5
1 3 5
1 1 4
1 5 4
2 7
2 2
2 4
2 3
2 4
2 2
2 2
2 10
Sample 1 Output
0
0
0
1
3
0
2
0
3
3
2