程序员 Xenia 有一个由 n 个节点组成的树。我们将考虑索引从 1 到 n 的树节点。我们还将考虑将第一个节点最初漆成红色,将其他节点漆成蓝色。
两个树节点 v 和 u 之间的距离是 v 和 u 之间最短路径中的边数。
Xenia 需要学习如何快速执行两种类型的查询:
1. 将指定的蓝色节点涂成红色;
2. 计算哪个红色节点最接近给定的节点,并打印到最近的红色节点的最短距离。
您的任务是编写一个程序来执行所描述的查询。
输入
第一行包含两个整数 n 和 m (2 ≤ n ≤ 105, 1 ≤ m ≤ 105) — 树中的节点数和查询数。接下来的 n - 1 行包含树的边,第 i 行包含一对整数 ai, bi (1 ≤ ai, bi ≤ n, ai ≠ bi) — 树的一条边。
接下来的 m 行包含查询。每个查询被指定为一对整数 ti, vi (1 ≤ ti ≤ 2, 1 ≤ vi ≤ n)。如果 ti = 1,那么作为对查询的回复,我们需要将蓝色节点 vi 涂成红色。如果 ti = 2,那么我们应该通过打印从某个红色节点到节点 vi 的最短距离来回复查询。
保证给定的图是一棵树并且所有查询都是正确的。
输出
对于每个第二种类型的查询,在一行中打印回复。
示例
输入 #1
5 4 1 2 2 3 2 4 4 5 2 1 2 5 1 2 2 5
输出 #1
0 3 2