← 返回题目列表

AtCoder · agc059_c

C. 尽可能长时间地猜测排列

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

分数: 1100 点

问题陈述

老师有一个隐藏的排列 P=(P_1,P_2,\ldots,P_N) of (1,2,\cdots,N)。 你将确定它。

为此,您准备了一系列整数对 (A_1,B_1),(A_2,B_2),\ldots,(A_{N(N-1)/2},B_{N(N-1)/2});这是所有形式对的排列 (a,b) (1 \le a < b \le N)。 现在,您将从头开始检查这些对。一对 (A_i, B_i),你会问是否 P_{A_i}<P_{B_i},老师会告诉你答案。 但是,如果您已经可以从之前的答案中确定该问题的答案,则您将跳过此问题。

求排列数 P,对于你的算法,你将不得不询问所有 \frac{N(N-1)}{2} 问题,模数 10^9+7.

约束

  • 2 \le N \leq 400
  • 1 \le A_i < B_i \le N
  • (A_i,B_i) \neq (A_j,B_j) (i \neq j)
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N
A_1 B_1
A_2 B_2
\vdots
A_{N(N-1)/2} B_{N(N-1)/2}

输出

打印答案。


示例输入 1

2
1 2

示例输出 1

2

显然,对于任何排列 P,你需要问 1 问题。


示例输入 2

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

示例输出 2

4

考虑 以 P=(2,3,1,4) 为例。 在这种情况下,您将跳过第三个问题,因为您知道 P_1 < P_2 和 P_1 > P_3 根据之前的问题,您可以确定 P_2 > P_3。 因此, P=(2,3,1,4) 不应计算在内。


示例输入 3

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

示例输出 3

0