题目描述

Berland 是一个道路系统并不发达的国家。Berland 一共有 $n$ 个城市和 $n-1$ 条双向道路，第 $i$ 条道路连接城市 $v_i$ 和 $u_i$。已知任意两个城市之间都可以只通过这些道路相互到达，也就是说，这些道路构成一棵树。

现在 Berland 正处于夜晚，一些道路需要打开照明。为了节约用电，法律禁止同时打开两条有公共端点的道路上的照明。居民们想知道，在不违反该法律的情况下，最多可以打开多少条道路的照明。

不幸的是，Berland 的一些道路可能会受到暴风雪影响，从而破坏一些城市之间的连通性。初始时没有任何道路受到暴风雪影响。接下来有 $q$ 个询问，分为两种：

1. 改变道路 $e_i$ 上的天气（$1\le e_i\le n-1$）：如果该道路当前没有暴风雪，则暴风雪开始；否则暴风雪结束。
2. 要求在所有能从城市 $x_i$ 出发、只经过没有暴风雪影响的道路而到达的城市所构成的连通块中，打开尽可能多的道路照明，并且仍然不能有两条被打开的道路有公共端点。换句话说，需要在城市 $x_i$ 所在的、由未受暴风雪影响道路组成的连通块中求解原问题。

输入格式

第一行包含一个整数 $g$（$0\le g\le 7$），表示当前测试点所属分组编号。

第二行包含一个整数 $n$（$2\le n\le 300000$），表示城市数量。

接下来 $n-1$ 行描述道路。第 $i$ 行包含两个整数 $v_i,u_i$（$1\le v_i,u_i\le n$），表示第 $i$ 条道路连接的两个城市。保证这些道路构成一棵树。

下一行包含一个整数 $q$（$1\le q\le 300000$），表示询问数量。

接下来 $q$ 行描述询问。第 $i$ 行首先包含一个整数 $t_i$（$1\le t_i\le 2$）。

• 如果 $t_i=1$，则这是第一类询问，后面跟一个整数 $e_i$（$1\le e_i\le n-1$），表示天气发生变化的道路编号。
• 如果 $t_i=2$，则这是第二类询问，后面跟一个整数 $x_i$（$1\le x_i\le n$），表示需要考虑从城市 $x_i$ 出发、只经过未受暴风雪影响道路可达的所有城市。

输出格式

对于每个第二类询问，输出一行，表示在城市 $x_i$ 所在连通块内最多可以打开多少条道路照明。

样例

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

3
4
3
1

样例解释

在样例中，Berland 初始结构如下：

初始树结构。

第一次询问后，城市 $7$ 和 $8$ 之间的道路发生暴风雪。随后询问城市 $1$，此时城市 $8$ 无法从城市 $1$ 到达，因此只考虑除城市 $8$ 外的所有城市。下面是一种最优开灯方案，打开照明的道路在原图中用红色标出：

第一次暴风雪后的最优开灯方案。

接下来的询问表示城市 $7$ 与 $8$ 之间道路上的暴风雪结束，结构恢复到初始状态。

最后一次询问中，从城市 $6$ 只能到达城市 $6,7,8$，因此最多只能在一条道路上打开照明，例如：

最后一次询问对应连通块的方案。

评分方式

本题测试点由 7 个分组组成。只有通过某一组及其要求的部分前置分组时，才能获得该组分数。注意，部分分组不要求通过样例。Offline-testing 表示该组测试结果只会在比赛结束后给出。