Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

G. Tree Queries

time limit per test

3 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou are given a tree consisting of *n* vertices (numbered from 1 to *n*). Initially all vertices are white. You have to process *q* queries of two different types:

- 1
*x*— change the color of vertex*x*to black. It is guaranteed that the first query will be of this type. - 2
*x*— for the vertex*x*, find the minimum index*y*such that the vertex with index*y*belongs to the simple path from*x*to some black vertex (a simple path never visits any vertex more than once).

For each query of type 2 print the answer to it.

Note that the queries are given in modified way.

Input

The first line contains two numbers *n* and *q* (3 ≤ *n*, *q* ≤ 10^{6}).

Then *n* - 1 lines follow, each line containing two numbers *x*_{i} and *y*_{i} (1 ≤ *x*_{i} < *y*_{i} ≤ *n*) and representing the edge between vertices *x*_{i} and *y*_{i}.

It is guaranteed that these edges form a tree.

Then *q* lines follow. Each line contains two integers *t*_{i} and *z*_{i}, where *t*_{i} is the type of *i*th query, and *z*_{i} can be used to restore *x*_{i} for this query in this way: you have to keep track of the answer to the last query of type 2 (let's call this answer *last*, and initially *last* = 0); then *x*_{i} = (*z*_{i} + *last*) *mod* *n* + 1.

It is guaranteed that the first query is of type 1, and there is at least one query of type 2.

Output

For each query of type 2 output the answer to it.

Example

Input

4 6

1 2

2 3

3 4

1 2

1 2

2 2

1 3

2 2

2 2

Output

3

2

1

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/25/2018 08:52:39 (d2).

Desktop version, switch to mobile version.

User lists

Name |
---|