There are $N$ rooted trees each consisting of a single vertex. The vertices are numbered from $1$ to $N$.

Write a program that performs the following queries:

• 1 u v: Add an edge between u and v. Here, v becomes the parent of u. Before the query is executed, u is the root of the tree containing u, and it is guaranteed that u and v belong to different trees.
• 2 v: Cut the edge connecting v and its parent. v is not the root.
• 3 u v: Print the LCA of u and v. u and v are in the same tree.

Input

The first line contains $N$ ($2 \le N \le 100{,}000$) and the number of queries $M$ ($1 \le M \le 200{,}000$).

The next $M$ lines each contain one query.

Output

For each type 3 query, print the result in order, one per line.

Examples

Input 1

5 9
3 1 1
1 1 2
1 3 2
1 4 3
3 1 4
3 3 4
2 4
1 5 3
3 1 5

Output 1

1
2
3
2