C. Dynamic lca
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.
  • lca $$$u$$$ $$$v$$$ $$$r$$$ — find the lowest common ancestor of $$$u$$$ and $$$v$$$ if we root their tree at $$$r$$$.

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, lca}) — 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 lca, then three integers $$$u,v,r$$$ ($$$1 \le u,v,r \le n$$$) follow — the two vertices and the root.

Output

For each of the queries of type lca, output the lowest common ancestor if $$$u,v,r$$$ are from the same tree; otherwise, output $$$-1$$$.

Example
Input
9 16
link 1 2
link 1 3
link 2 5
link 5 4
link 5 6
link 7 2
link 8 6
link 9 2
lca 8 9 4
lca 8 9 5
lca 8 9 1
cut 3
link 6 7
lca 8 9 4
lca 8 9 5
lca 8 9 1
Output
5
5
2
6
6
2