有一棵由 $N$ 个顶点构成的树（无向无环连通图）。顶点编号为 $1$ 到 $N$，边编号为 $1$ 到 $N-1$。最初，所有顶点的颜色均为白色。

请编写一个程序处理以下两种查询：

• 1 i：改变第 $i$ 个顶点的颜色（白色 $\to$ 黑色，黑色 $\to$ 白色）。
• 2 v：输出从顶点 $1$ 到顶点 $v$ 的路径上第一个黑色顶点的编号。若不存在这样的顶点，则输出 $-1$。

输入格式

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

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

接下来一行给出查询的个数 $M$（$1 \le M \le 100{,}000$）。

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

输出格式

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

样例

样例输入 1

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

样例输出 1

-1
8
-1
2
-1