402588: GYM100814 C Connecting Graph

Memory Limit:1024 MB Time Limit:6 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

C. Connecting Graphtime limit per test6 secondsmemory limit per test1024 megabytesinputstandard inputoutputstandard output

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.

Input

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)

Output

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.

ExamplesInput
1
4 5
1 1 2
2 1 2
1 2 3
2 1 3
2 1 4
Output
1
3
-1
Note

Warning: large Input/Output data, be careful with certain languages.

加入题单

上一题 下一题 算法标签: