题目描述

一个国家的领土中，有 $n$ 座城市和 $m$ 条道路。这 $m$ 条道路将 $n$ 座城市连通，即任意两座城市存在道路直接或间接可达。两座城市之间可能有多条道路，但不存在一条道路两端连通同一座城市。

该国家要选定一些城市，重点发展。具体而言，每个城市有一个重要值 $a_i$，其中 $a_i=0$ 表示城市不需要重点发展，如果 $a_i=1$ 表示城市需要重点发展。初始时所有 $a_i=0$。

该国家有 $q$ 次规划，每次规划会选定一个城市 $x$，令 $a_x \gets 1-a_x$。

每次规划后，作为首席规划师的你要求出这样的城市 $p$ 的数量，使得 $a_p=0$，且城市 $p$ 消失（连带与城市 $p$ 直接相连的道路一起消失）后，任意满足 $a_u=a_v=1$ 的两个城市 $u,v$ 均存在道路直接或间接可达。

需要注意，规划只是在纸面上假想的，并不会真的删去任何城市。

输入格式

输入的第一行包含由空格隔开的三个正整数 $n,m,q$。

接下来的 $m$ 行，每行包含两个正整数 $u,v$，描述一条连接 $u,v$ 两座城市的双向道路。

接下来的 $q$ 行，每行包含一个正整数 $x$，描述一次规划。

输出格式

输出 $q$ 行，每行包含一个非负整数，代表每次修改后问题的答案。

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

3
2
3
1
3
4

提示

【样例解释】

以第四次规划为例，此时需要重点发展的城市为 $1$ 和 $4$，那么 $a_p=0$ 的城市只有 $2$ 和 $3$。如果城市 $2$ 消失，那么存在路径 $1-3-4$。如果城市 $3$ 消失，那么 $1$ 和 $4$ 互相不可到达。所以满足条件的城市只有 $2$，答案为 $1$。

【数据范围】

• 对于 $15\%$ 的数据，$n,q \le 300$，$m \le 500$。
• 对于另外 $15\%$ 的数据，$m=n-1$，且对于所有道路，$v=u+1$。
• 对于另外 $20\%$ 的数据，$m=n-1$。

对于所有数据，$2 \le n \le 10^5$，$n-1\le m \le 2 \times 10^5$，$1 \le q \le 2 \times 10^5$，$1 \le u,v,x \le n$，$u \neq v$。