Alex is known to be very clever, but Walter does not believe that. In order to test Alex, he invented a new game. He gave Alex n nodes, and a list of queries. Walter then gives Alex one query every second, there are two types of queries:
means: adding an undirected edge between nodes u and v.
means: what was the earliest time (query index) when u and v became connected? 2 nodes are connected if there is a path of edges between them. Alex can solve this problem easily, but he is too busy now, so he is asking for your help.
The first line contains an integer T, the number of test cases. Each test case begins with a line containing two integers (1 ≤ n, m ≤ 105), the number of nodes and queries, respectively. Then there are m lines, each line represents a query and contains three integers, type, u and v (
, 1 ≤ u, v ≤ n)
For each query of type 2, print one line with one integer, the answer to the query. If the 2 nodes in the query are not connected, print -1.
1
4 5
1 1 2
2 1 2
1 2 3
2 1 3
2 1 4
1
3
-1
Warning: large Input/Output data, be careful with certain languages.
