Queries on Graph
After previous 2 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 N nodes. At each query you add an edge between 2 nodes (bidirectional edge) or you have to calculate a distance between 2 nodes. Assume that every time graph doesn’t contain any loops and cycles.
1) Add edge between 2 nodes and the length of this edge is 1. This query is represented as “1 i j”
2) Output the distance between i-th and j-th node, if there is no path between those nodes output -1. This query is represented as “2 i j”
Input
You are given an integer N (1 ≤ N ≤ 100000) - the number of nodes and Q (1 ≤ Q ≤ 100000) - the number of queries. The next Q lines contain one query each, of one of the above forms.
Output
For each query of the type “2 i j” print the distance between i-th and j-th node. If there is no path between those nodes output -1.