DYNALCA - Dynamic LCA

有一个森林最初由 $n (1 \le n \le 100000)$ 个互不相连的点构成 你需要处理以下操作： - **link A B**：添加从顶点A到B的边，使A成为B的子节点，其中保证A是一个根顶点，A和B在不同的树中。 - **cut A**：切断点A到其父节点的边，保证A是一个非根节点。 - **lca A B**：输出A和B的最近共同祖先，保证A和B在同一棵树中。 感谢@Chtholly_Nota 提供的翻译

A forest of rooted trees initially consists of N (1 You must process the following queries, where (1 - **link** A B : add an edge from vertex A to B, making A a child of B, where initially A is a root vertex, A and B are in different trees. - **cut** A : remove edge from A to its parent, where initially A is a non-root vertex. - **lca** A B : print the lowest common ancestor of A and B, where A and B are in the same tree.

The first line of input contains the number of initial single-vertex trees N and the number of queries M (1

For each **lca** query output the lowest common ancestor (vertex number between 1 and N).

5 9
lca 1 1
link 1 2
link 3 2
link 4 3
lca 1 4
lca 3 4
cut 4
link 5 3
lca 1 5

1
2
3
2