鉄道運賃 (Train Fare)

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\) 年間の住民の満足度調査それぞれにおいて，鉄道会社に不満を抱く住民がいる都市の数を計算しておきたい．

課題

JOI 国の鉄道路線の情報と，運賃の値上げ計画が与えられたとき，それぞれの満足度調査において鉄道会社に不満を抱く住民がいる都市の数を求めるプログラムを作成せよ．

標準入力から以下の入力を読み込め．

• \(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\) 年目の満足度調査で不満を抱く住民がいる都市の数を出力せよ．

すべての入力データは以下の条件を満たす．

• \(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 点]

追加の制限はない．

JOI 2016 · JCIOI · CC BY-SA 4.0