Lowest common ancestor in a dynamic forest

Time limit2sMemory limit512 MB

Summary

Maintain a forest of rooted trees under link, cut, and lowest-common-ancestor queries, printing each LCA.

Level: Hard9 of 10
Topics: Tree, Linked list, Graph, DFS
Solved: No attempts yet

Problem

There are N rooted trees, and each one consists of a single vertex. The vertices are numbered 1 to N, so at the start every vertex is the root of its own one vertex tree.

Write a program that processes the following three kinds of queries in the given order.

1 u v: add one edge between u and v, and v becomes the parent of u. Right before this query is processed, u is the root of the tree that contains it, and u and v belong to different trees.
2 v: remove the edge between v and its parent. v is not a root. After the removal, v becomes the root of a new tree.
3 u v: print the lowest common ancestor of u and v. At the moment this query is processed, u and v belong to the same tree. u and v may be equal, and then the answer is u.

Input

The first line contains the number of vertices N and the number of queries M. ( $2 \le N \le 100000$ , $1 \le M \le 200000$ )

Each of the next M lines contains one query in the format described above.

Output

For every query of type 3, print its answer on its own line, in the order the queries are given.

Examples6

Example 1

Input

Expected output

Example 2
Input
```
2 1
3 1 1
```
Expected output
```
1
```

Example 3

Input

Expected output

Example 4

Input

Expected output

Example 5

Input

Expected output

Example 6

Input

Expected output