Dynamic Forest

You need to manage 3 types of queries:

1. Add an edge to the graph (link).

2. Remove an edge from the graph (cut).

3. For two vertices a and b, determine the length of the path between them (or return -1 if they belong to different connected components) (get).

Initially, the graph is empty, consisting of N vertices and no edges. It is guaranteed that the graph remains a forest at all times. When adding an edge, it is ensured that the edge is not already present in the graph. When removing an edge, it is ensured that the edge exists in the graph.

Input

The input begins with two numbers, N and M (1 ≤ N ≤ 10^5+1, 1 ≤ M ≤ 10^5), representing the number of vertices and the number of queries, respectively. This is followed by M lines, each containing a command (link, cut, or get) and 2 numbers ranging from 1 to N, indicating the vertex numbers involved in the query.

Output

For each get query, output a single number: the distance between the specified vertices, or -1 if they are in separate connected components.

Examples