Submit | All submissions | Best solutions | Back to list |

## QTREE3 - Query on a tree again! |

English | Vietnamese |

You are given a tree (an acyclic undirected connected graph) with N nodes. The tree nodes are numbered from 1 to N. In the start, the color of any node in the tree is white.

We will ask you to perfrom some instructions of the following form:

**0 i**: change the color of the i-th node (from white to black, or from black to white);

or**1 v**: ask for the id of the first black node on the path from node 1 to node v. if it doesn't exist, you may return -1 as its result.

### Input

In the first line there are two integers **N** and **Q**.

In the next **N**-1 lines describe the edges in the tree: a line with two integers **a b** denotes an edge between **a** and **b**.

The next **Q** lines contain instructions **"0 i"** or **"1 v"** (1 ≤ i, v ≤ N).

### Output

For each "**1 v**" operation, write one integer representing its result.

### Example

Input:9 8 1 2 1 3 2 4 2 9 5 9 7 9 8 9 6 8 1 3 0 8 1 6 1 7 0 2 1 9 0 2 1 9Output:-1 8 -1 2 -1

### Constraints & Limits

There are 12 real input files.

For 1/3 of the test cases, N=5000, Q=400000.

For 1/3 of the test cases, N=10000, Q=300000.

For 1/3 of the test cases, N=100000, Q=100000.

Added by: | Fudan University Problem Setters |

Date: | 2008-06-14 |

Time limit: | 2s |

Source limit: | 50000B |

Memory limit: | 1536MB |

Cluster: | Cube (Intel G860) |

Languages: | All except: ERL JS-RHINO NODEJS PERL6 SCM qobi VB.NET |

Resource: | VNOI Marathon '08 - Round 6/DivA Problem Setter: Blue Mary |