시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2.5 초 | 256 MB | 117 | 52 | 49 | 44.144% |
JOI 国には N 個の都市があり,それぞれ 1, 2, . . . , N の番号が付けられている.都市 1 は JOI 国の首都である.
また,JOI 国には鉄道会社がひとつだけあり,この会社は M 個の路線を運行している.これらの路線にはそれぞれ 1, 2, . . . , M の番号が付けられており,i 番目 (1 ≦ i ≦ M) の路線は都市 Ui と都市 Vi を双方向に結んでいる.都市と都市の間を鉄道以外で移動することはできない.また,どの都市からどの都市へもいくつかの路線を乗り継いで移動することができるようになっている.
現在,どの路線の運賃も 1 円である.経営不振に陥った鉄道会社は,今後 Q 年間かけていくつかの路線の運賃を値上げする計画を立てた.この計画では,計画開始から j 年目 (1 ≦ j ≦ Q) の年初めに路線 Rj の運賃を 1 円から 2 円に値上げする予定である.値上げされた路線の運賃は,その後ずっと 2 円のままであり,再び値上げすることはない.
ところで,この鉄道会社では,毎年,各都市の住民の満足度調査を行っている.計画開始前は,どの都市の住民もこの鉄道会社に満足しているが,値上げによって不満を持つ住民が現れる可能性がある.
それぞれの年の満足度調査は,その年の値上げの実施後に行う.したがって,j 年目 (1 ≦ j ≦ Q) の満足度調査は,路線 R1, R2, . . . , Rj の運賃の値上げは完了し,それ以外の路線の運賃は値上げされていない状態で行われることになる.j 年目 (1 ≦ j ≦ Q) の満足度調査では,都市 k (2 ≦ k ≦ N) の住民は,以下の条件が満たされるとき,そしてそのときに限り鉄道会社に不満を抱く.
ただし,いくつかの路線を使って移動するときの費用は,それぞれの路線の運賃の合計である.また,都市 1 の住民が鉄道会社に対して不満を抱くことはない.値上げ後の運賃で最小の費用を達成する経路は,計画開始前の運賃で最小の費用を達成する経路と異なる可能性があることに注意せよ.
計画の実行に先立って,今後 Q 年間の住民の満足度調査それぞれにおいて,鉄道会社に不満を抱く住民がいる都市の数を計算しておきたい.
JOI 国の鉄道路線の情報と,運賃の値上げ計画が与えられたとき,それぞれの満足度調査において鉄道 会社に不満を抱く住民がいる都市の数を求めるプログラムを作成せよ.
標準入力から以下の入力を読み込め.
標準出力に Q 行で出力せよ.j 行目 (1 ≦ j ≦ 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
この入力例では,計画開始前,及びそれぞれの満足度調査の時点でのそれぞれの都市から都市 1 への運 賃は,以下の表のようになる.
時点 | 都市 2 | 都市 3 | 都市 4 | 都市 5 |
---|---|---|---|---|
計画開始前 | 1 | 1 | 2 | 2 |
1 年目 | 1 | 1 | 2 | 2 |
2 年目 | 1 | 2 | 2 | 3 |
3 年目 | 1 | 2 | 2 | 3 |
4 年目 | 2 | 2 | 3 | 3 |
5 年目 | 2 | 2 | 4 | 3 |
例えば,3 年目の満足度調査では,都市 3 と都市 5 の住民が不満を抱くので,出力の 3 行目には 2 を出 力する.
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