DYNALCA - Dynamic LCA
A forest of rooted trees initially consists of N (1 ≤ N ≤ 100,000) single-vertex trees. The vertices are numbered from 1 to N.
You must process the following queries, where (1 ≤ A, B ≤ N) :
- 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.
Input
The first line of input contains the number of initial single-vertex trees N and the number of queries M (1 ≤ M ≤ 100,000). The following M lines contain queries.
Output
For each lca query output the lowest common ancestor (vertex number between 1 and N).
Example
Input:
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
Output:
1
2
3
2
Added by: | indy256 |
Date: | 2011-05-02 |
Time limit: | 2s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |