鉄道運賃 (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 提供的翻译

[problemUrl]: https://atcoder.jp/contests/joi2016ho/tasks/joi2016ho_c JOI 国には $ N $ 個の都市があり，それぞれ $ 1,\ 2,\ \ldots,\ N $ の番号が付けられている．都市 $ 1 $ は JOI 国の首都である． また，JOI 国には鉄道会社がひとつだけあり，この会社は $ M $ 個の路線を運行している．これらの路線にはそれぞれ $ 1,\ 2,\ \ldots,\ M $ の番号が付けられており，$ i $ 番目 ($ 1\ \leqq\ i\ \leqq\ M $) の路線は都市 $ U_i $ と都市 $ V_i $ を双方向に結んでいる．都市と都市の間を鉄道以外で移動することはできない．また，どの都市からどの都市へもいくつかの路線を乗り継いで移動することができるようになっている． 現在，どの路線の運賃も $ 1 $ 円である．経営不振に陥った鉄道会社は，今後 $ Q $ 年間かけていくつかの路線の運賃を値上げする計画を立てた．この計画では，計画開始から $ j $ 年目 ($ 1\ \leqq\ j\ \leqq\ Q $) の年初めに路線 $ R_j $ の運賃を $ 1 $ 円から $ 2 $ 円に値上げする予定である．値上げされた路線の運賃は，その後ずっと $ 2 $ 円のままであり，再び値上げすることはない． ところで，この鉄道会社では，毎年，各都市の住民の満足度調査を行っている．計画開始前は，どの都市の住民もこの鉄道会社に満足しているが，値上げによって不満を持つ住民が現れる可能性がある． それぞれの年の満足度調査は，その年の値上げの実施後に行う．したがって，$ j $ 年目 ($ 1\ \leqq\ j\ \leqq\ Q $) の満足度調査は，路線 $ R_1,\ R_2,\ \ldots,\ R_j $ の運賃の値上げは完了し，それ以外の路線の運賃は値上げされていない状態で行われることになる．$ j $ 年目 ($ 1\ \leqq\ j\ \leqq\ Q $) の満足度調査では，都市 $ k $ ($ 2\ \leqq\ k\ \leqq\ N $) の住民は，以下の条件が満たされるとき，そしてそのときに限り鉄道会社に不満を抱く． - その時の運賃で都市 $ k $ から首都である都市 $ 1 $ へ移動するときの費用の最小値が，計画開始前の運賃で都市 $ k $ から都市 $ 1 $ へ移動するときの費用の最小値よりも大きい． ただし，いくつかの路線を使って移動するときの費用は，それぞれの路線の運賃の合計である．また，都市 $ 1 $ の住民が鉄道会社に対して不満を抱くことはない．値上げ後の運賃で最小の費用を達成する経路は，計画開始前の運賃で最小の費用を達成する経路と異なる可能性があることに注意せよ． 計画の実行に先立って，今後 $ Q $ 年間の住民の満足度調査それぞれにおいて，鉄道会社に不満を抱く住民がいる都市の数を計算しておきたい．

標準入力から以下の入力を読み込め． - $ 1 $ 行目には，$ 3 $ 個の整数 $ N,\ M,\ Q $ が空白を区切りとして書かれている．これらは，JOI 国には $ N $ 個の都市と $ M $ 個の路線があり，運賃の値上げ計画が $ Q $ 年間に渡ることを表している． - 続く $ M $ 行のうちの $ i $ 行目 ($ 1\ \leqq\ i\ \leqq\ M $) には，$ 2 $ 個の整数 $ U_i,\ V_i $ が空白を区切りとして書かれている．これらは，$ i $ 番目の路線が都市 $ U_i $ と都市 $ V_i $ を結んでいることを表している． - 続く $ Q $ 行のうちの $ j $ 行目 ($ 1\ \leqq\ j\ \leqq\ Q $) には，整数 $ R_j $ が書かれている．これは，計画の $ j $ 年目に路線 $ R_j $ の運賃を値上げすることを表している．

標準出力に $ Q $ 行で出力せよ．$ j $ 行目 ($ 1\ \leqq\ j\ \leqq\ Q $) には，$ j $ 年目の満足度調査で不満を抱く住民がいる都市の数を出力せよ． - - - - - -

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

0
2
2
4
4

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

1
1
2
2
3
3

2 1 1
1 2
1

1

### 課題 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\ <\ k\ \leqq\ Q $)． - どの $ 2 $ つの都市についても，それらを直接結ぶ路線は $ 1 $ 個以下である． - どの都市についても，その都市から都市 $ 1 $ までいくつかの路線を使って移動することができる． ### 小課題 #### 小課題 1 \[12 点\] 以下の条件を満たす． - $ N\ \leqq\ 100 $． - $ M\ \leqq\ 4\,950 $． - $ Q\ \leqq\ 30 $． #### 小課題 2 \[14 点\] - $ Q\ \leqq\ 30 $ を満たす． #### 小課題 3 \[35 点\] - 正しい出力に現れる整数は $ 50 $ 種類以下である． #### 小課題 4 \[39 点\] 追加の制限はない． - - - - - - ### Sample Explanation 1 この入力例では，計画開始前，及びそれぞれの満足度調査の時点でのそれぞれの都市から都市 $ 1 $ への運賃は，以下の表のようになる． !\[2016-ho-t1-fig01.png\](https://img.atcoder.jp/joi2016ho/2016-ho-t1-fig01.png) 例えば，$ 3 $ 年目の満足度調査では，都市 $ 3 $ と都市 $ 5 $ の住民が不満を抱くので，出力の $ 3 $ 行目には $ 2 $ を出力する． - - - - - - ### Sample Explanation 2 \- - - - - -