AT_joi2016ho_c 鉄道運賃 (Train Fare)

JOI 国有 $N$ 个城市，编号分别为 $1, 2, \ldots, N$ 。城市 $1$ 是 JOI 国的首都。 JOI 国只有一家铁路公司，该公司在 JOI 国内共有 $M$ 条线路，这些线路编号分别为 $1, 2, \ldots, M$ 。每条线路都可看作一条无向边，线路 $i(1\leqslant i\leqslant N)$ 连接城市 $U_i$ 和 $V_i$ 。假设你只能依靠铁路运输在不同的城市间来往。当然你可以换乘不同线路。保证任意两个城市间都有线路直接或间接连接。 目前，任何线路的票价是 1 日元。该公司经营不善，只好计划在未来 $Q$ 年里提高票价。从提价计划开始的第 $j$ 年初 $(1\leqslant j\leqslant Q)$ ，线路 $R_j$ 的票价会从 1 日元升至 2 日元。 之后该线路票价一直保持在 2 日元，不会再提高。 该公司每年都会对每个城市的居民进行满意度调查。在提价计划开始之前，任何一个城市的居民都对该公司感到满意。但由于价格上涨，可能有一些城市的居民会不满。每年的满意度调查都在当年提价后进行。因此，计划开始后第 $j$ 年 $(1\leqslant j\leqslant Q)$ 进行满意度调查时，线路 $R_1,R_2,\ldots,R_j$ 已经提价，剩余线路的票价暂无变化。 在第 $j$ 年的满意度调查中，如果**当年城市 $k(2\leqslant k\leqslant N)$ 到首都的最低总票价 大于 提价计划开始前城市 $k$ 到首都的最低总票价**，城市 $k$ 的居民会对铁路公司感到不满。 使用多条路线的费用是每条路线的运费的总和。首都人民不会对该公司感到不满。提价后最低费用的路线可能与计划开始前最低费用的路线有所不同。

第一行有三个整数 $N, M, Q$ ，用空格分隔。 在接下来的 $M$ 行中，第 $i(1\leqslant i\leqslant M)$ 行有两个整数 $U_i, V_i$ ，用空格分隔。 在接下来的 $Q$ 行中，第 $j(1\leqslant i\leqslant Q)$ 行有一个整数 $R_j$ 。

输出共 $Q$ 行，第 $j(1\leqslant i\leqslant Q)$ 行有一个整数，表示在计划开始后第 $j$ 年的满意度调查中，有多少个城市的居民对铁路公司不满。 #### 来源 JOI 2015/2016 T3，译者 @[Planet6174](/space/show?uid=29762) 感谢@Planet6174 提供的翻译

### 課題 JOI 国の鉄道路線の情報と，運賃の値上げ計画が与えられたとき，それぞれの満足度調査において鉄道会社に不満を抱く住民がいる都市の数を求めるプログラムを作成せよ． - - - - - - ### 制限 すべての入力データは以下の条件を満たす． - $ 2\ \leqq\ N\ \leqq\ 100\,000 $． - $ 1\ \leqq\ Q\ \leqq\ M\ \leqq\ 200\,000 $． - $ 1\ \leqq\ U_i\ \leqq\ N $ ($ 1\ \leqq\ i\ \leqq\ M $)． - $ 1\ \leqq\ V_i\ \leqq\ N $ ($ 1\ \leqq\ i\ \leqq\ M $)． - $ U_i\ \neq\ V_i $ ($ 1\ \leqq\ i\ \leqq\ M $)． - $ 1\ \leqq\ R_j\ \leqq\ M $ ($ 1\ \leqq\ j\ \leqq\ Q $)． - $ R_j\ \neq\ R_k $ ($ 1\ \leqq\ j\