{"problem":{"name":"国土规划","description":{"content":"一个国家的领土中，有 $n$ 座城市和 $m$ 条道路。这 $m$ 条道路将 $n$ 座城市连通，即任意两座城市存在道路直接或间接可达。两座城市之间可能有多条道路，但不存在一条道路两端连通同一座城市。 该国家要选定一些城市，重点发展。具体而言，每个城市有一个重要值 $a_i$，其中 $a_i=0$ 表示城市不需要重点发展，如果 $a_i=1$ 表示城市需要重点发展。初始时所有 $a_i=0$。 ","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10517"},"statements":[{"statement_type":"Markdown","content":"一个国家的领土中，有 $n$ 座城市和 $m$ 条道路。这 $m$ 条道路将 $n$ 座城市连通，即任意两座城市存在道路直接或间接可达。两座城市之间可能有多条道路，但不存在一条道路两端连通同一座城市。\n\n该国家要选定一些城市，重点发展。具体而言，每个城市有一个重要值 $a_i$，其中 $a_i=0$ 表示城市不需要重点发展，如果 $a_i=1$ 表示城市需要重点发展。初始时所有 $a_i=0$。\n\n该国家有 $q$ 次规划，每次规划会选定一个城市 $x$，令 $a_x \\gets 1-a_x$。\n\n每次规划后，作为首席规划师的你要求出这样的城市 $p$ 的数量，使得 $a_p=0$，且城市 $p$ 消失（连带与城市 $p$ 直接相连的道路一起消失）后，任意满足 $a_u=a_v=1$ 的两个城市 $u,v$ 均存在道路直接或间接可达。\n\n需要注意，规划只是在纸面上假想的，并不会真的删去任何城市。\n\n## Input\n\n输入的第一行包含由空格隔开的三个正整数 $n,m,q$。\n\n接下来的 $m$ 行，每行包含两个正整数 $u,v$，描述一条连接 $u,v$ 两座城市的双向道路。\n\n接下来的 $q$ 行，每行包含一个正整数 $x$，描述一次规划。\n\n## Output\n\n输出 $q$ 行，每行包含一个非负整数，代表每次修改后问题的答案。\n\n[samples]\n\n## Note\n\n**【样例解释】**\n\n以第四次规划为例，此时需要重点发展的城市为 $1$ 和 $4$，那么 $a_p=0$ 的城市只有 $2$ 和 $3$。如果城市 $2$ 消失，那么存在路径 $1-3-4$。如果城市 $3$ 消失，那么 $1$ 和 $4$ 互相不可到达。所以满足条件的城市只有 $2$，答案为 $1$。\n\n**【数据范围】**\n\n- 对于 $15\\%$ 的数据，$n,q \\le 300$，$m \\le 500$。\n- 对于另外 $15\\%$ 的数据，$m=n-1$，且对于所有道路，$v=u+1$。\n- 对于另外 $20\\%$ 的数据，$m=n-1$。\n\n对于所有数据，$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$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10517","tags":["洛谷原创","O2优化","洛谷月赛","圆方树"],"sample_group":[["4 4 6\n1 2\n2 3\n3 1\n3 4\n1\n3\n3\n4\n4\n1","3\n2\n3\n1\n3\n4"]],"created_at":"2026-03-03 11:09:25"}}