A. Dynamic get_path
time limit per test
7 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given a forest on $$$n$$$ vertices, initially without edges.

You are also given $$$q$$$ queries of three types:

  • link $$$u$$$ $$$v$$$ — add a new undirected edge between $$$u$$$ and $$$v$$$.
  • cut $$$i$$$ — cut the edge that was added during the $$$i$$$-th query.
  • get_path $$$u$$$ $$$v$$$ — find the length of the path $$$u \leftrightarrow v$$$.

It is guaranteed that integers $$$i$$$ are distinct and that the graph remains a forest.

Input

The first line contains two integers $$$n$$$ and $$$q$$$ ($$$2 \le n,q \le 2\cdot 10^5$$$) — the number of vertices and the number of queries, respectively.

The $$$j$$$-th of the following $$$q$$$ lines describes a query according to the following principle:

First, a single string $$$type$$$ is given ($$$type \in$$$ {link, cut, get_path}) — the type of the query.

If $$$type$$$ is link, then two integers $$$u,v$$$ ($$$1 \le u,v \le n$$$) follow, meaning that a new undirected edge between $$$u$$$ and $$$v$$$ is added.

If $$$type$$$ is cut, then a single integer $$$i$$$ ($$$1 \le i \lt j \le q$$$) follows — the index of the query that added the edge that is required to be removed.

If $$$type$$$ is get_path, then two integers $$$u,v$$$ ($$$1 \le u,v \le n$$$) follow — the endpoints of a queried path.

Output

For each of the queries of type get_path, output the length of the path if it exists; otherwise, output $$$-1$$$.

Example
Input
9 12
link 1 2
link 2 3
get_path 1 3
cut 2
get_path 1 3
link 8 7
link 8 9
link 2 8
get_path 9 3
get_path 9 2
link 3 1
get_path 9 3
Output
2
-1
-1
2
4