親切な迷路 Swift編（paizaランク A 相当）
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
下記の問題をプログラミングしてみよう！
子供遊園地のディレクターとなった paiza 君はちびっこ全員がゴールできるような親切設計の迷路を作ることにしました。迷路には 1 ~ N までの番号が振られた N 個のエリアがあり、そのうち他のエリアから向けられた通路が存在しないエリアをスタート、他のエリアに向けた通路が存在しないエリアをゴールとします。スタート・ゴールは 1 つとは限らない点に注意してください。
各エリアからは他のエリアに向けて一方通行の通路を用意することにしました。
エリアと通路の草案が完成したところで、paiza 君は次の 2 点について確認することにしました。
・通路を進んでいけばどのエリアからでも迷わずゴールできる設計になっているかどうか
・スタートからゴールまで全部で何通りの行き方が存在するか
迷路についての情報が与えられるのでこの 2 点について調査を行なってください。
なお、迷わない迷路とは「任意のエリア X から通路 R_1, ... R_y を順に進んだときに再びエリア X に到着するような通路の順列 R_1, ..., R_y が存在せず、スタートからゴールできる迷路」であるものとします。
例として入力例 1 の迷路は以下の通りであり、スタートは 1,6, ゴールは 2,5,6 となります。
- 入力される値
-
N K
D_1 T_1
...
D_K T_K
・1 行目では与えられる迷路のエリアの個数 N, 通路の数 K が半角スペース区切りで与えられます。
・続く K 行のうち i 行目では i 番の通路の始発点のエリア番号 D_i と終着点のエリア番号 T_i が半角スペース区切りで与えられます。(1 ≦ i ≦ K)
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
judge
G_1 roots_num_1
...
・1 行目では、迷わずゴールできる迷路になっている場合は "Yes" を、なっていない場合は "No" を出力してください。
・迷わずゴールできる場合は 2 行目以降に「エリア番号が小さいゴールから順に」ゴールのエリアの番号 G_1 とスタートからそのゴールまでの行き方の数 roots_num_i を 1000000007 で割った余りを出力してください。半角スペース区切りで出力してください。
- 条件
-
すべてのテストケースにおいて、以下の条件をみたします。
・ 1 ≦ N ≦ 5000
・ 1 ≦ M ≦ min(N × (N - 1) / 2, 100000)
・ 1 ≦ D_i, T_i ≦ N (1 ≦ i ≦ K)
- 入力例1
-
6 5
1 2
1 3
3 4
3 5
4 5
- 出力例1
-
Yes
2 1
5 2
6 1
- 入力例2
-
5 9
5 4
5 3
5 2
5 1
1 2
1 3
1 4
2 3
2 1
- 出力例2
-
No
