Queries on Graph#7248
After previous problems, you see that our hero likes problems on queries. He is presenting to you a new problem. It is like a shortest-path problem on dynamic graph.
You are given nodes. At each query you add an edge between nodes (bidirectional edge) or you have to calculate a distance between nodes. Assume that every time graph doesn't contain any loops and cycles.
1) Add edge between nodes and the length of this edge is . This query is represented as "1 i j"
2) Output the distance between -th and -th node, if there is no path between those nodes output . This query is represented as "2 i j"
You are given an integer (1 \leq N \leq 100000) - the number of nodes and (1 \leq Q \leq 100000) - the number of queries. The next lines contain one query each, of one of the above forms.
For each query of the type "2 i j" print the distance between -th and -th node. If there is no path between those nodes output .
Example 1