$N$个顶点构成的树（无向无环连通图）。顶点编号为 $1$ 到 $N$，边编号为 $1$ 到 $N-1$。初始时所有顶点均为黑色。

请编写程序执行以下两种查询：

• 1 i：翻转第 $i$ 个顶点的颜色（白色 $\to$ 黑色，黑色 $\to$ 白色）。
• 2 v：输出所有白色顶点 $u$ 与 $v$ 之间的距离中的最近距离。其中 $u$ 和 $v$ 可以相同。若 $v$ 为白色则答案为 $0$。若树中没有白色顶点，则输出 $-1$。

输入格式

第一行给出 $N$ ($2 \le N \le 100{,}000$)。

接下来 $N-1$ 行，每行给出第 $i$ 条边连接的两个顶点编号 $u$ 和 $v$。

下一行给出查询个数 $M$ ($1 \le M \le 100{,}000$)。

接下来 $M$ 行，每行给出一个查询。

输出格式

对于每个 $2$ 号查询，按顺序每行输出一个结果。

样例

输入

10
1 2
1 3
2 4
1 5
1 6
4 7
7 8
5 9
1 10
10
1 6
1 6
1 6
2 3
1 1
1 1
2 3
2 10
2 4
2 6

输出

2
2
2
3
0