## 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 5Output:1

2

3

2

Added by: | Andrey Naumenko |

Date: | 2011-05-02 |

Time limit: | 0.367s |

Source limit: | 50000B |

Memory limit: | 1536MB |

Cluster: | Cube (Intel G860) |

Languages: | All except: ASM64 |