Xenia 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.

The first line contains two integers n and m (2 \le n \le 105,1 \le m \le 105) - 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 ai,bi (1 \le ai,bi \le n,ai \neq bi) - an edge of the tree.

Next m lines contain queries. Each query is specified as a pair of integers ti,vi (1 \le ti \le 2,1 \le vi \le n). If ti=1, then as a reply to the query we need to paint a blue node vi in red. If ti=2, then we should reply to the query by printing the shortest distance from some red node to node vi.

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

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