文件读写

• 输入文件car.in
• 输出文件car.out

限制

• 1000ms
• 128MB

题目描述

徐老师最近很喜欢玩《极品飞车》，体验飙车的快乐，风驰电掣！

这天他打开了游戏中的一个新地图，这个地图一共有 $n$ 个检查点和 $n-1$ 条道路，不同的检查点之间可以通过道路直接或间接到达

现在徐老师在这个地图里驾驶着他自己改装的爱车—— AMG Mistarl LaFerrari Aperta Veneno Roadster 疯狂漂移

玩了半天的他回过神来发现这个地图居然需要知道自己通过每个检查点的次数才能通关！

于是他只能向你求助

他希望你能够实现一个动态记录系统，让他在随心所欲漂移的过程中，自动记录每个检查点的通过次数！

徐老师会在每次开始漂移前告诉你他会从 $x$ 号检查点一路漂移到达 $y$ 号检查点

并且在这之间他会询问你到现在为止某个检查点被通过的次数

输入格式

输入第一行包含一个整数 $n$，表示检查点数量

接下来 $n-1$ 行，每行包含两个整数 $u,v$ 表示 $u,v$ 之间存在一条边

接下来一行包含一个整数 $T$ 表示徐老师接下来有 $T$ 次行为

接下来 $T$ 行，每行包含一组数据表示徐老师的一次行为，行为分两种：漂移 和 查询

• 对于 漂移，徐老师会给出三个数据 1 x y 表示这次他会从 $x$ 号检查点出发到达 $y$ 号检查点
• 对于 查询，徐老师会给出两个数据 2 x，表示查询到现在为止 $x$ 号检查点被他经过的次数

输出格式

对于每次 查询，输出结果

数据范围

对于 $40\%$ 的数据，$1 \leq n,T \leq 100$

对于 $100\%$ 的数据，$1 \leq n,T \leq 1000,1 \leq x,y \leq n$。

样例输入

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

样例输出

2
1
3
2

样例解释

第一次漂移徐老师的路径是 $3->2->1->4$ 第二次漂移徐老师的路径是 $1->2$ 此时查询 $1$ 号检查点被经过 $2$ 次, $4$ 号检查点被经过 $1$ 次 第三次漂移徐老师的路径是 $4->1->2$ 此时查询 $1$ 号检查点被经过 $3$ 次，$4$ 号检查点被经过 $2$ 次