D - 徒競走 Editorial /

Time Limit: 3 sec / Memory Limit: 256 MB

問題文

N 匹のうさぎがいます。 うさぎは 1 から N まで番号が振られています。

これら N 匹のうさぎが徒競走をしました。 同着はいませんでした。 このとき、着順は N! 通り考えられます。

高橋君は M 人の観客から情報を集めました。 i 番目の観客によると、うさぎ x_i はうさぎ y_i よりも先にゴールしたそうです。

すべての観客の情報に合致するような着順が何通り考えられるか求めてください。

制約

  • 2≦N≦16
  • 1≦M≦N(N-1)/2
  • 1≦x_i，y_i≦N
  • x_i≠y_i
  • (x_i，y_i) の組はすべて相異なる。
  • すべての観客の情報に合致するような着順が少なくともひとつ存在する。

部分点

  • 30 点分のテストケースでは、N≦8 を満たす。

入力

入力は以下の形式で標準入力から与えられる。

N M
x_1 y_1
x_2 y_2
:
x_M y_M

出力

すべての観客の情報に合致するような着順が何通り考えられるか出力せよ。

入力例1

3 2
2 1
2 3

出力例1

2

次の 2 通りが考えられます。

  • (2，1，3)
  • (2，3，1)

入力例2

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

出力例2

3

次の 3 通りが考えられます。

  • (1，2，3，4，5)
  • (1，2，4，3，5)
  • (1，4，2，3，5)

入力例3

16 1
1 2

出力例3

10461394944000

答えは 32 bit 整数型に収まらない場合があります。 なお、このケースは部分点のテストケースには含まれません。