eolymp
bolt
Try our new interface for solving problems
Problems

Queries on Graph

Queries on Graph

Time limit 1 second
Memory limit 64 MiB

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 data

You are given an integer N (1N100000) - the number of nodes and Q (1Q100000) - the number of queries. The next Q lines contain one query each, of one of the above forms.

Output data

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.

Examples

Input example #1
5 6
1 1 2
1 2 3
2 1 3
2 1 5
1 2 5
2 1 5
Output example #1
2
-1
2
Author Mahammad Valiyev
Source Local Contest #2 Qafqaz University by Mahammad Valiyev