C - Guessing Permutation for as Long as Possible Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 1100 点

問題文

先生が (1,2,\cdots,N) の順列 P=(P_1,P_2,\ldots,P_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} であるかを尋ね、先生が答えを教えます。 ただし、この質問への答えがそれ以前の答えから特定できる場合は、この質問を省略します。

このアルゴリズムで \frac{N(N-1)}{2} 個の質問がすべてされるような順列 P の個数を 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 に対しても、質問を一つする必要があります。

入力例 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

Score : 1100 points

Problem Statement

A teacher has a hidden permutation P=(P_1,P_2,\ldots,P_N) of (1,2,\cdots,N). You are going to determine it.

To do this, you prepared a sequence of pairs of integers (A_1,B_1),(A_2,B_2),\ldots,(A_{N(N-1)/2},B_{N(N-1)/2}); this is a permutation of all pairs of the form (a,b) (1 \le a < b \le N). Now, you will go over the pairs from the beginning. For a pair (A_i, B_i), you will ask if P_{A_i}<P_{B_i}, and the teacher will tell you the answer. However, you will skip this question if you can already determine the answer to it from previous answers.

Find the number of permutations P, for which with your algorithm you will have to ask all \frac{N(N-1)}{2} questions, modulo 10^9+7.

Constraints

  • 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)
  • All values in the input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

Print the answer.

Sample Input 1

2
1 2

Sample Output 1

2

Clearly, for any permutation P, you need to ask 1 question.

Sample Input 2

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

Sample Output 2

4

Consider P=(2,3,1,4) as an example. In this case, you will skip the third question since you know P_1 < P_2 and P_1 > P_3 from previous questions and you can determine P_2 > P_3. Therefore, P=(2,3,1,4) should not be counted.

Sample Input 3

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

Sample Output 3

0