← 返回题目列表

AtCoder · abc041_d

D. 竞走

中文机器翻译题面 查看原题

問題文

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 它可能不适合整数类型。请注意,此案例不包含在部分评分测试案例中。