← 返回题目列表

Codeforces · 342/E

E. 齐妮亚和树

中文机器翻译题面 查看原题

程序员 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