시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 256 MB 0 0 0 0.000%

문제

There are N students. For 1 <= i <= N, the i-th student scores i points from the exam. These students are divided into groups. In the beginning, each group contains exactly one student. More specifically, initially, the i-th student is in group i. 

You have write a program that supports the following operations: 

  1. Group Merge: in this operation you are given two group numbers X and Y, and you want to merge group Y into group X. After the merge, every student in group Y will be in group X, and group Y no longer exists. 
  2. Query: in this operation you are given an integer J, and you want to find the rank of the J-th student in her/his group. In a group, the student who gets the highest score has rank 1, the student with the second highest score has rank 2, and so on. 

For each test case, there will be L operations. 

입력

The first line of the input contains an integer T (T <= 5) denoting the number of test cases. Then T test cases follow in the format described next. 

  • The first line of the test case contains integers N and L (1 <= N <= 100,000; 1 <= L <= 200,000). 
  • The next L lines describe the operations in the following format: 
    • The first integer K in the line specifies the type of the operation. 
    • If K = 1, it is the Group Merge operation. Then, on the same line, there will be 2 more integers X and Y. You program has to merge students from group Y into group X. 
    • If K = 2, it is the Query operation. Then an integer J is given. You have to output the rank of the J-th student in her/his group.

출력

For each test case, you have to output, for every Query operation, the rank of the J-th student. 

예제 입력

2
3 5
2 2
1 2 3
2 2
1 1 2
2 2
4 4
1 1 2
1 1 3
1 1 4
2 2

예제 출력

1
2
2
3

힌트