【题目描述】
C 城有n 个旅游景点，编号分别为1 到n。它们被n 􀀀 1 条双向道路连接起来，形成了一棵树的结构。热爱旅行的小A 想为自己的假期做些打算。对于两个景点u; v，小A 定义f (u; v)为u 到v 唯一的简单路径上，编号最小的景点的编号。由于某些原因，小A 对f 值较小的路径有着特殊的偏爱，因此他希望自己选择的旅游路线的f 尽量小。为了规划最优路线，小A 进行了若干次如下操作：
1 x：小A 标记了编号为x 的景点。初始时，所有景点都是未标记的。
2 x：小A 想知道，如果他现在从x 景点出发，前往一个已被标记的景点y，f (x; y)的最小值是多少。
你能准确地回答出小A 的所有疑问吗？
【输入格式】
从文件sith.in 中读入数据。
第一行两个正整数n; q，表示景点的数量和小A 操作的数量。
接下来n 􀀀 1 行，每行两个正整数u; v，表示景点u 和景点v 之间有一条双向道路。
接下来q 行，每行两个整数，描述了小A 的一次操作，格式如题目所述。
保证对于所有的2 操作，一定存在一个被标记过的景点。
【输出格式】
输出到文件sith.out 中。
对于每个2 操作，输出一行一个整数，表示最小的f (x; y)。
【样例1 输入】
4 6
1 2
2 3
3 4
1 3
1 3
2 3
1 3
2 2
2 1
【样例1 输出】
3
2
1
【子任务】
对于10% 的数据，n, q <= 50；
对于20% 的数据，n, q <=300；
对于30% 的数据，n, q <=2000；
对于另外20% 的数据，保证与每个景点连接的道路不超过两条；
对于另外20% 的数据，数据随机生成；
对于100% 的数据，1<= n,q <=10^5，保证至少有一个2 操作。