给定一棵包含 $n$ 个顶点的树。每个顶点都可以放置一个筹码。初始时，所有顶点均为空。

你需要处理两种类型的查询：

1. 在一个顶点放置一个筹码。
2. 从一个顶点移除筹码。

每次查询后，你需要输出当前筹码配置的跨度（span）。

跨度定义为将所有筹码移动到同一个顶点所需的最少操作次数。在一次操作中，你可以将一个筹码从其所在顶点移动到任意相邻顶点。当然，在此过程中，一个顶点可以同时包含多个筹码。

注意，这些操作仅用于定义跨度，实际上并不会执行。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 10^5$)，表示树的顶点数。

接下来的 $n-1$ 行描述树的边，每行包含两个整数 $u$ 和 $v$ ($1 \le u, v \le n$)，表示第 $i$ 条边连接的两个顶点索引。

保证这些边构成一棵树。

下一行包含一个整数 $q$ ($1 \le q \le 10^5$)，表示查询次数。

接下来的 $q$ 行描述查询，每行一个。每个查询描述为 “$c \ v$” ($1 \le v \le n$)。字符 $c$ 为 “+” 表示第一类查询，为 “-” 表示第二类查询。整数 $v$ 是查询所作用的顶点索引。保证如果查询是第一类，则 $v$ 号顶点当前没有筹码；如果查询是第二类，则 $v$ 号顶点当前有筹码。同时保证每次查询后树中至少有一个筹码。

输出格式

对于每次查询，输出一行，包含一个整数：应用该查询后树的跨度。

样例

输入 1

3
1 2
2 3
4
+ 1
+ 3
+ 2
- 1

输出 1

0
2
2
1

输入 2

6
1 2
2 3
3 4
4 5
2 6
5
+ 1
+ 4
+ 5
- 5
+ 6

输出 2

0
3
4
3
4