SP8791 DYNALCA - Dynamic LCA

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).