胡须

题目描述

对于一个由n个点，n-1条边组成的树，当这个树除了根节点外所有节点最多只有一个子节点时，Z君把它定义为胡须树。

这个树每条边要么是黑色的要么是白色的。对于给定的胡须树，有以下三种操作：

• 1. 把第i条边染黑，保证这条边之前是白色的。

• 2. 把第i条边染白，保证这条边之前是黑色的。

• 3. 输出点i到j的最短路径长，要求路径上的边都是黑色的。如果不存在这样的路径，输出-1。

初始时，所有边都是黑色的。

输入

只有一组数据。

第一行为一个整数n，表示点的个数。点的编号为1..n。$ (2\le n\le10^{5}) $

接下来n-1行，每行两个整数u v，表示一条边。第i个输入的边的编号即为i。

接下来一行为一个整数m，表示操作的个数。$ (1\le m\le3·10^{5}) $

接下来m行，每行第一个数字表示操作类型，具体如上所述。

输入

对于第三种操作，输出相应的答案。

输入样例一

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

输出样例一

1
2
1
1
-1
-1

输入样例二

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

输出样例二

3
-1
3
2

说明

这道题有两个难度版本。对于容易版本，保证操作1和操作2一定在所有的操作3之前。只要解决容易版本（即得分大于等于0.5）即算通过本题。

样例解释

对于样例一，节点1和节点2通过编号为1的边连接，节点2和节点3通过通过编号为2的边连接。