题目描述

译自 JOI Open 2013 T2 「同期 / Synchronization」

JOI 公司在全球共有 $N$ 台服务器，每台服务器都包含一份不同的重要信息。JOI 公司决定在服务器之间铺设线路，使得信息可以在服务器之间共享。当两台服务器之间有线路铺设时，它们就可以互相传递信息。另外，从一台服务器出发，通过经过一些已经铺设的线路，也可以到达其他的服务器并与之交换信息。

服务器上装有高性能的同步系统，当两台服务器可以互相传递信息，并且它们拥有的信息不同的时候，就会自动进行同步。当服务器 $A$ 和 $B$ 之间进行同步时，$A$ 和 $B$ 的信息就会变成同步前 $A$ 和 $B$ 至少一方拥有的所有信息。

为了节省成本，可以铺设的线路数量限制为 $N-1$ 条。当所有的线路都铺设好时，从每台服务器出发，都有且仅有一种方法可以传递信息到其他所有的服务器，而且不会经过同一台服务器两次以上。

最初（时刻 $0$）时，没有任何线路被铺设。而且由于线路铺设的地点有一些极其恶劣的条件（沙漠，海底等），线路有可能变得无法使用。当线路变得无法使用时，直到重新铺设之前都不能使用这条线路。

现在，已知在时刻 $j\ (1 \leq j \leq M)$ 时，恰好有一条线路的状态发生了变化。你想要知道某些服务器在时刻 $M+1$ 时，拥有的不同信息有多少种。

给定可以铺设的线路以及线路的铺设情况，编写一个程序，求出一些服务器拥有的不同信息的种类数。

输入格式

第一行包含三个用空格分隔的整数 $N, M, Q$，分别表示服务器的台数，线路的铺设情况的信息的个数，想要求出拥有信息种类数的服务器的台数。

接下来的 $N-1$ 行中，第 $i$ 行 $(1 \leq i \leq N-1)$ 包含两个用空格分隔的整数 $X_{i}, Y_{i}$，表示线路 $i$ 连接了服务器 $X_{i}$ 和 $Y_{i}$。

接下来的 $M$ 行中，第 $j$ 行 $(1 \leq j \leq M)$ 包含一个整数 $D_{j}$，表示在时刻 $j$ 时，线路 $D_{j}$ 的铺设状态发生了变化。也就是说，在时刻 $j$ 之前，如果线路 $D_{j}$ 没有被铺设，那么它就会被新铺设，如果已经被铺设，那么它就会变得无法使用。在时刻 $j$ 发生线路状态变化之后，到时刻 $j+1$ 为止，所有的同步都会完成。

接下来的 $Q$ 行中，第 $k$ 行 $(1 \leq k \leq Q)$ 包含一个整数 $C_{k}$，表示最终想要知道服务器 $C_{k}$ 拥有多少种信息。

输出格式

输出 $Q$ 行。第 $k$ 行 $(1 \leq k \leq Q)$ 输出一个整数，表示服务器 $C_{k}$ 最终拥有的信息的种类数。

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

3
5
4

数据范围与提示

对于所有输入数据，满足：

• $2 \leq N \leq 10^5$
• $1 \leq M \leq 2\times 10^5$
• $1 \leq Q \leq N$
• $1 \leq X_{i},Y_{i} \leq N, X_{i} \neq Y_{i}\ (1 \leq i \leq N-1)$
• $1 \leq D_{j} \leq N-1\ (1 \leq j \leq M)$
• $1 \leq C_{k} \leq N\ (1 \leq k \leq Q)$
• $C_{k}$ 的值互不相同
• 如果所有的线路都被铺设了，那么任意两台不同的服务器之间都可以通过至少一条线路进行通信

详细子任务附加限制及分值如下表所示。