#2520. 树上查询 II

树上查询 II

Description

有一棵NN 个节点的树,节点编号为1N1 ~N 。将dist(a,b)dist(a , b )定义为从节点aa 到节点bb 路径上的边数。每个节 点都有一个颜色,白色或黑色。最初所有节点都是黑色的。执行以下两 种操作:①00 ii ,更改第ii 个节点的颜色(从黑色变为白色,或从白色 变为黑色);②11 vv ,查询与vv 最近的白色节点的距离dist(u,v)dist(u , v ), 节点uu 必须是白色的(uu 可以等于vv )。显然,只要节点vv 为白色,则 结果将始终为00

Format

Input

11行有一个整数NN105N (N ≤10^5 ),表示节点数。在接下来 的N1N -1行中,每行都包含两个整数aba、b ,表示在aa bb 之间有一条 边。下一行有一个整数QQ105Q (Q ≤10^5 ),表示指令数。接下来的QQ 行, 每行都包含指令“00 ii ”或“11 vv ”。

Output

对每个查询操作,都单行输出结果。若树中没有白色节 点,则输出“1-1”。

Samples

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

来源

SPOJQTREE5