树上的操作查询

给定一棵包含 $N$ 个顶点的树。顶点编号为 1 到 $N$。
每个顶点上有一个变量 $A_i$，初始时 $A_i = 0\ (1 \le i \le N)$。

你需要处理 $Q$ 次查询。每个查询有以下三种类型之一：

操作类型 1：1 u v

以顶点 $u$ 为根，将树重新定根。
考虑以顶点 $v$ 为根的子树，将该子树中所有顶点 $i$ 的 $A_i$ 均加一。

操作类型 2：2 u v

在树中找到从顶点 $u$ 到顶点 $v$ 的唯一简单路径。
对于路径上的每个顶点 $i$，令 $A_i$ 加一。

操作类型 3：3 v

计算并输出：

其中 $dist(x, y)$ 表示顶点 $x$ 到顶点 $y$ 之间的边数。

输入格式

第一行输入一个整数 $N$，表示顶点数。$(1 \le N \le 2 \times 10^5)$

接下来 $N - 1$ 行，每行两个整数 $u, v$，表示一条无向边。
保证输入构成一棵树。

然后输入一个整数 $Q$，表示查询的数量。$(1 \le Q \le 2 \times 10^5)$

接下来 $Q$ 行，每行描述一个查询，格式如上所述。
保证至少存在一个类型为 3 的查询。

输出格式

对于每个类型为 3 的查询，输出一行一个整数表示答案。

示例

输入

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

输出

1
5

部分分

数据