CF342E.Xenia and Tree

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:

1. paint a specified blue node in red;
2. 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.

程序员 Xenia 有一棵包含 $n$ 个节点的树。我们将树的节点编号为 $1$ 到 $n$。初始时，第 $1$ 号节点被涂成红色，其余所有节点均被涂成蓝色。

树中两个节点 $v$ 和 $u$ 之间的距离定义为连接 $v$ 与 $u$ 的最短路径所含边的数量。

Xenia 需要学习如何快速处理以下两类查询：

1. 将指定的一个蓝色节点涂成红色；
2. 计算距离给定节点最近的红色节点，并输出到该最近红色节点的最短距离。

你的任务是编写一个程序来执行上述查询。

The first line contains two integers n and m (2 ≤ n ≤ 105, 1 ≤ m ≤ 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 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.

第一行包含两个整数 $n$ 和 $m$（$2 \leq n \leq 10^5$，$1 \leq m \leq 10^5$）—— 分别表示树中节点的数量和查询的数量。接下来的 $n-1$ 行描述树的边，其中第 $i$ 行包含一对整数 $a_i,\,b_i$（$1 \leq a_i,\,b_i \leq n$，$a_i \neq b_i$）—— 表示树中的一条边。

接下来的 $m$ 行包含查询。每个查询由一对整数 $t_i,\,v_i$（$1 \leq t_i \leq 2$，$1 \leq v_i \leq n$）指定。若 $t_i = 1$，则需将蓝色节点 $v_i$ 染为红色；若 $t_i = 2$，则需回答从任意一个红色节点到节点 $v_i$ 的最短距离。

保证所给图是一棵树，且所有查询均合法。

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

对于每个第二类查询，请在单独一行中输出回答。