You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

移动机器人

题目背景

小明对机器人非常感兴趣，因此他加入了学校的机器人兴趣班。

题目描述

小明最近制作了一个机器人，这个机器人可以在一张特定的地图上进行移动。这张地图包括 $n$ 个结点和 $n-1$ 条边，且保证任意两个结点之间直接或者间接相连。

小明的机器人支持完成两种指令：

（1）向机器人发出移动指令，指令包含两个整数 $x$ 和 $y$，此时机器人将从指定点 $x$ 沿 着边移动到另一个指定点 $y$；

（2）向机器人发出查询指令，指令包含一个整数 $x$，此时机器人统计当前已经经过 $x$ 点多少次。

输入格式

第一行输入两个正整数 $n,q$，代表城市数量和操作次数。

接下来 $n-1$ 行，每行输入两个正整数 $x$ 和 $y$，代表从点 $x$ 到点 $y$ 存在一条边。

接下来 $q$ 行，每行输入一个指令。

• 若为 1 x y,则代表让机器人从点 $x$ 到点 $y$。
• 若为 2 x，则代表查询点 $x$ 被经过的次数（依次查询，不需要统计之后的指令）。

输出格式

针对每一个 $2$ 指令，输出一个整数代表经过的次数。

样例 #1

样例输入 #1

4 4
1 2
2 3
1 4
1 3 4
1 1 2
2 1
2 4

样例输出 #1

2
1

样例输入 #2

5 5
1 2
2 3
3 4
4 5
1 1 5
1 2 4
2 3
2 2
2 5

样例输出 #2

2
2
1

样例输入 #3

3 3
1 2
2 3
1 1 3
2 1
2 2

样例输出 #3

1 
1

提示

【样例解释】

第一条指令机器人从 $3$ —>$2$ —> $1$ —> $4$;

第二条指令机器人从 $1$ —> $2$;

对于第一个询问，$1$ 号点被走过 $2$ 次;

对于第二个询问，$4$ 号点被走过 $1$ 次;

【数据范围】

对于 $40\%$ 的数据，$1<=n<=100，1<=q<=100$。

对于 $100\%$ 的数据，$1<=n<=1000,1<=q<=1000，1<=x<=n，1<=y<=n$。

大样例： sample.in

sample.out