0950 - 魔女っ娘ヒナくるん -Magic.08

なんか提出ファイルの容量に制限あってテストケースアップできてないです。
取り敢えず簡単なIOのみ投稿してあります。

Magic.08 『Spider Web』

前回のあらすじ

襲来する岩を突破したヒナくるんとアヤ。

地底の底が見えてきたその時、ヒナくるんは糸に絡め取られるのであった・・・

本編

アヤ

「ヒナ、大丈夫！？」

ヒナくるん

「大丈夫に見える？この糸、体力が吸われていくわ・・・」

？？？

「私のおもてなしは、喜んでいただけたかしら？」

アヤ

「何だお前偉そうに」

？？？

「私はヤヌメ。コティーヤ様の命により、貴女をここで止めさせていただきます。」

ヒナくるん

「凄い読みづらい名前ね。ヤヌメですか（笑）」

ヤヌメ

「・・・殺す！！」

問題

ヤヌメを怒らせてしまったヒナくるん。

今回は、ヤヌメを倒すことが目標となる。

この問題では、最初にヤヌメがN個の独立した糸を飛ばし、

Mターンにおいて処理が行われる。

各糸1-Nまでの番号が振られており、糸一つはヒナくるんの体力を１減らす。

各ターンおいて、糸Aと糸Bが繋がり、その糸は強固となり、ヒナくるんの体力は繋がっている糸の数だけ減る。

つまりC個の糸が繋がっている場合、ヒナくるんの体力はC減少する。

さて、ヒナくるんは回避するのに精一杯だ。

ヒナくるんは、最初に一定量の体力を保持しており、任意のターンにおいて、その時に最も受けるダメージが少ない糸の固まりに被弾する。

ヒナくるんの体力は、０を最小とする。

さて、ヒナくるんがMターンヤヌメの攻撃を耐え凌げばヤヌメは魔力切れを起こし、ヒナくるんの勝利が確定する。

あなたには、ヒナくるんの戦いの経過を求めるプログラムを作成してもらいたい。

ヤヌメが飛ばす糸の数、処理を行うターン数、ヒナくるんの体力、

各ターンにおいての糸の連結情報が与えられるので、

各ターン終了後においてのヒナくるんの体力を出力せよ。

もしも体力が0以下になってしまった場合は、それは放送事故 に他ならないので、

そのターン以降は"Broadcasting accident"を出力すること。

入出力形式

一行目に、ヤヌメの飛ばす糸の数、処理を行うターン数、ヒナくるんの体力 N,M,H が空白区切り与えられる。

続いてM行に渡り、連結された糸 A,B が空白区切りで与えられる。

N M H
A1 B1
A2 B2
..
AM BM

各ターンでの入力の後、

その段階でのヒナくるんの体力 P を改行込みで出力せよ。

もしヒナくるんの体力が尽きている場合は、"Broadcasting accident"と改行込みで出力せよ。

P

制約

• 1 ≦ N ≦ 100,000
• 1 ≦ M ≦ min(N*N/3　,　1,000,000)
• 0 ≦ H ≦ 10,000,000
• 1 ≦ A,B ≦ N
• 入力される数値は全て整数である。

入出力例

入力例

10 9 9
1 2
3 4
5 6
7 8
9 10
2 3
6 7
2 9
10 8

出力例

8
7
6
5
3
1
Broadcasting accident
Broadcasting accident
Broadcasting accident