场上用的原题即为 Easy Ver。

时间限制： 5.0 秒

空间限制： 1024 MB

题目背景

小 z 想要环游世界，现在他来到了 A 国。

题目描述

A 国有 $n$ 座城市（编号为 $1$ 到 $n$），由 $n - 1$ 条双向道路相连，保证任意两座城市之间都由道路直接或间接相连。

小 z 有 $m$ 个开车旅游计划，每个旅游计划用 $(s_i, t_i)$ 描述，表示从 $s_i$ 号城市出发沿最短路径去到 $t_i$ 号城市。

小 z 发现 A 国的基建水平非常糟糕，经过观察：

• 初始所有道路都没有被翻修。
• 经过一条没有翻修的道路会爆一个轮胎。
• 小 z 有一个备用轮胎。如果备胎是好的，小 z 可以将损坏的轮胎更换后继续移动；如果备胎是已经更换下来的轮胎，车将无法移动。
• 有 $k$ 座城市里有维修站，小 z 可以在那里把所有轮胎修好。
• 初始所有轮胎都是好的。

对于一个旅游计划 $(s_i, t_i)$，如果车能从 $s_i$ 成功开到 $t_i$，那么旅游计划是可行的。

给定 $q$ 次事件：

• $1\ u\ v$，连接 $u, v$ 的道路进行了翻修，保证这条路存在且之前没有被翻修。
• $2$，询问有多少旅游计划可行。

小 z 希望能够及时得到信息，所以本题强制在线，你需要对于每个询问事件立即回答。

输入格式

从标准输入读入数据。

记录 $\text{lastans}$ 为上一次询问事件的答案，初始 $\text{lastans} = 0$。

读入一行两个整数 $n, X$。$X$ 是强制在线的加密参数。

接下来 $n - 1$ 行，每行读入两个整数 $u, v$，表示城市 $u$ 和 $v$ 之间有一条道路。

读入一行一个整数 $k$。

接下来一行，读入 $k$ 个整数，表示有维修站的城市，保证这 $k$ 个城市互不相同。

读入一行一个整数 $m$。

接下来 $m$ 行，第 $i$ 行读入两个整数 $s_i, t_i$，表示有一个从 $s_i$ 到 $t_i$ 的旅游计划，保证 $s_i\ne t_i$。

读入一行一个整数 $q$。

接下来 $q$ 行，每行先读入一个正整数 $op$：

• 若 $op = 1$，表示发生 $1$ 事件，接下来读入两个整数 $u', v'$，实际的 $u = u'\oplus (X\times \text{lastans}), v = v'\oplus (X\times \text{lastans})$。$\oplus$ 表示异或操作。
• 若 $op = 2$，表示发生 $2$ 事件。

事件含义同上文描述。

输出格式

输出到标准输出。

对于每一个询问事件，输出一行一个整数，表示有多少个旅游计划可行。

5 0
1 2
3 4
1 5
2 3
5
4 3 1 2 5
3
5 2
2 5
1 3
7
2
1 2 3
1 1 5
1 1 2
1 3 4
2
2

3
3
3

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

2
2
2
2
6

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

1
1

5 0
2 3
1 4
1 2
3 5
1
2
5
5 2
3 5
2 3
2 3
5 4
5
2
1 1 4
1 1 2
2
1 2 3

3
3

样例 5

见题目文件区的 5.in 和 5.ans。

样例 5 解释

该样例满足子任务 3 的限制。

样例 6

见题目文件区的 6.in 和 6.ans。

样例 6 解释

该样例满足子任务 4 的限制。

子任务

本题采用捆绑测试，你只有通过一个子任务中的所有测试点才能得到该子任务的分数。

所有数据满足，$2\le n\le 1\times 10^5,\ 1\le m\le 1\times 10^5,\ 1\le q\le 2\times 10^5,\ 1\le k\le 20,\ X\in \{0, 1\}$，保证输入数据合法。

子任务编号	分值	$n,m\le$	$k\le$	$q\le$	$X\in$
1	10	$10$			$\{0, 1\}$
2	20	$100$	$20$	$100$	$\{0,1\}$
3	30	$10^5$		$2\times 10^5$	$\{0\}$
4	40				$\{0,1\}$