Codeforces Round 199 (Div. 2) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only 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.

data structures

divide and conquer

trees

*2400

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. Xenia and Tree

time limit per test

5 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputXenia the programmer has a tree consisting of *n* nodes. We will consider the tree nodes indexed from 1 to *n*. We will also consider the first node to be initially painted red, and the other nodes — to be painted blue.

The distance between two tree nodes *v* and *u* is the number of edges in the shortest path between *v* and *u*.

Xenia needs to learn how to quickly execute queries of two types:

- paint a specified blue node in red;
- calculate which red node is the closest to the given one and print the shortest distance to the closest red node.

Your task is to write a program which will execute the described queries.

Input

The first line contains two integers *n* and *m* (2 ≤ *n* ≤ 10^{5}, 1 ≤ *m* ≤ 10^{5}) — the number of nodes in the tree and the number of queries. Next *n* - 1 lines contain the tree edges, the *i*-th line contains a pair of integers *a*_{i}, *b*_{i} (1 ≤ *a*_{i}, *b*_{i} ≤ *n*, *a*_{i} ≠ *b*_{i}) — an edge of the tree.

Next *m* lines contain queries. Each query is specified as a pair of integers *t*_{i}, *v*_{i} (1 ≤ *t*_{i} ≤ 2, 1 ≤ *v*_{i} ≤ *n*). If *t*_{i} = 1, then as a reply to the query we need to paint a blue node *v*_{i} in red. If *t*_{i} = 2, then we should reply to the query by printing the shortest distance from some red node to node *v*_{i}.

It is guaranteed that the given graph is a tree and that all queries are correct.

Output

For each second type query print the reply in a single line.

Examples

Input

5 4

1 2

2 3

2 4

4 5

2 1

2 5

1 2

2 5

Output

0

3

2

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/22/2024 07:35:25 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|