圣诞节快到了！家人们正忙着购买装饰用的常青树。这棵圣诞树包含 $n$ 个节点，编号从 $0$ 到 $n-1$，根节点为 $0$。Alice 和 Bob 正在玩这棵新树，他们通过这棵树来消磨时间。Alice 将拿着一支彩色标记笔，而 Bob 会发出两种类型的指令：

• $+x$，这意味着 Alice 将给编号为 $x$ 的节点涂色。
• $-x$，这意味着 Alice 将清除编号为 $x$ 的节点的颜色。

在执行完每一条指令后，Alice 都需要找出当前所有已涂色节点的最近公共祖先（定义见下文）。你能帮 Alice 尽快回答 Bob 的问题吗？

输入格式

你的程序将在一个或多个测试用例上进行测试。输入的第一行是一个整数 $T$，表示测试用例的数量（$1 \le T \le 100$）。接下来是 $T$ 个测试用例。每个测试用例的第一行包含一个整数 $N$，表示树中的节点数（$1 \le N \le 10^5$）。接下来的 $N-1$ 行，每行包含一对整数 $x$ 和 $y$，中间用空格隔开（$0 \le x, y \le N-1$），表示节点 $x$ 和节点 $y$ 之间有一条边。保证给定的边构成一棵树。接下来的一行包含一个整数 $Q$，表示 Bob 发出的指令数量（$1 \le Q \le 4 \times 10^5$）。接下来的 $Q$ 行，每行包含一条 Bob 发出的指令，格式为 $q_i \ a_i$，其中 $q_i \in \{+, -\}$ 且 $0 \le a_i \le N-1$。保证清除指令只会应用于已涂色的节点，而涂色指令只会应用于未涂色的节点。

输出格式

对于 Bob 发出的每一条指令，输出一行，包含一个整数，表示当前所有已涂色节点的最近公共祖先；如果当前没有已涂色的节点，则输出 -1。

样例

样例输入 1

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

样例输出 1

2
6
0
6
6
1
1

说明

在图论和计算机科学中，树或有向无环图（DAG）中两个节点 $v$ 和 $w$ 的最近公共祖先（LCA）是距离根节点最远且同时是 $v$ 和 $w$ 的祖先的节点，其中我们定义每个节点都是其自身的祖先。