1. paizaラーニングトップ
  2. レベルアップ問題集
  3. DAG・メモ化再帰メニュー(言語選択)
  4. 問題一覧 D(Beta)編
  5. 仕事の順序 D(Beta)編

DAG・メモ化再帰メニューのサムネイル
仕事の順序 D(Beta)編(paizaランク A 相当)

問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう!

問題

下記の問題をプログラミングしてみよう!

ぱいじょ株式会社で働いている京子ちゃんは、 N 個の仕事を抱えています。 i 番目の仕事を仕事 i と呼びます。仕事には k 個の順序関係があり、仕事 J_i が終わると、仕事 W_i に取り掛かることができます。仕事 N に取り掛かるために、取り組む必要のある仕事の順序は何通りありますか?答えは非常に大きくなることがあるので、 1,000,000,007 で割ったあまりを出力してください。

ここで、取り組む仕事の順序 A と B が異なるとは以下の場合のことを指します。


  • 仕事の順序 A で取り組む仕事を順に X_1, X_2, ... X_N とし、仕事の順序 B で取り組む仕事を順に Y_1, Y_2, ... Y_M とします。 N ≠ M または X_i ≠ Y_i となる i が存在する場合



また、それぞれの仕事は適切な順序で必ず取り掛かることができ、すべての仕事に取り組む必要はありません。

入力される値

N k
J_1 W_1
J_2 W_2
...
J_k W_k


・ 1 行目に、仕事の総数 N と仕事の順序関係の個数 k が与えられます。
・ 2 行目から k + 1 行目にかけて、 J_i と W_i が与えられます。仕事 J_i が終わると、仕事 W_i に取り掛かることができます。


入力値最終行の末尾に改行が1つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
期待する出力

仕事 N に取り掛かるために、取り組む必要のある仕事の順序は何通りありますか?答えは非常に大きくなることがあるので、 1,000,000,007 で割ったあまりを出力してください。

また、末尾に改行を入れ、余計な文字、空行を含んではいけません。

条件

すべてのテストケースにおいて、以下の条件をみたします。

・ 入力はすべて整数
・ 2 ≦ N ≦ 10,000
・ N - 1 ≦ k ≦ Min(N * (N - 1 ) / 2, 100,000 )
・ 1 ≦ J_i < W_i ≦ N
・ J_i ≠ W_i
・ J_i = J_j かつ W_i = W_j となる i, j の組み合わせは存在しない
・ それぞれの仕事は適切な順序で必ず取り掛かることができる

入力例1

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

出力例1

3

入力例2

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

出力例2

3

入力例3

4 5
1 2
1 3
2 3
2 4
3 4

出力例3

3

問題一覧へ戻る

ページの先頭へ戻る