Lowest common ancestor in a dynamic forest

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.

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.

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