0845 - 魔女っ娘ヒナくるん -Magic.05

Magic.05 『Outsiders』

前回のあらすじ

メディス退治に成功し、魔女っ娘としての第一歩を踏み出したヒナくるん！

ヒナくるんの勝利を祝い、希望を伝えるため、アヤよ、空高く舞い上がれ！

本編

アヤ

「号外だよ！号外だよ！

　魔女っ娘ヒナくるん、華麗に誕生！

　幻想郷の平穏は、彼女が守る！

　厄神だからと侮るなかれ！今の彼女はミラクル魔女っ娘！

　文々。新聞、号外だよー！！」

ヒナ

「あなたテンション高いわね・・・」

アヤ

「この騒ぎに乗じて自分の新聞の株をあげれるかもしれないからね！

　ちゃっかり便乗させてもらうわよ！」

問題

ミラクルが伝わる。ヒナクルが広がる。

アヤは、ヒナくるんの誕生を広めようとしている。

アヤは風の道を使うことで、高速に移動することができる。

風の道は、一方通行であり、移動には時間を 1 要する。

アヤが使うことが出来る風の道と、

アヤが移動しようとする場所が与えられるので、

移動に必要な最短移動時間を出力せよ。

もし移動ができない場合は、それは放送事故に他ならない。

入出力形式

一行目に、アヤが訪れる場所の数 N , 風の通り道の数 M が空白区切りで与えられる。

続いてN行に渡り、風がどの場所を繋いでいるかを示す情報 a , b が空白区切りで与えられる。

風は、a から b に一方通行である。

続いて、アヤが移動したい範囲 s , g が与えられる。

s と g が共に 0 の時、入力の終了とする。

N M
a1 b1
a2 b2
..
..
aM bM
s g
s g
..
..
0 0

s , g の入力毎に、s から g に移動する際の最短移動時間を出力せよ。

移動不可能な場合は、"Broadcasting accident"を出力せよ。

制約

• 1 ≦ N ≦ 1000
• 0 ≦ M ≦ N*(N-1)/2
• 1 ≦ a , b , s , g ≦ N
• s , g の入力の数は 1000000 を超えない。
• 入力の経路に閉路は発生しない。

入出力例

入力例

7 7
1 2
1 3
2 4
2 5
4 7
5 6
6 7
1 2
2 6
2 7
1 3
3 7
7 2
0 0

出力例

1
2
2
1
Broadcasting accident
Broadcasting accident