Ex - Balance Scale Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MB

配点 : 650 点

問題文

1,2, \dots,N の番号の付いた N 個のおもりがあります。
これから天秤を用いて M 回の重さの比較を行います。

  • 比較開始前に、空文字列 S を用意する。
  • i 回目の比較では、左の皿におもり A_i のみを、右の皿におもり B_i のみを乗せる。
  • この際、以下の 3 通りのうちいずれかの結果が得られる。
    • おもり A_i の方がおもり B_i より重い。
      • この際 S の末尾に > を加える。
    • おもり A_i とおもり B_i は同じ重さである。
      • この際 S の末尾に = を加える。
    • おもり B_i の方がおもり A_i より重い。
      • この際 S の末尾に < を加える。
  • 天秤が誤った結果を出すことはない。

実験終了後、長さ M の文字列 S が得られます。
>, =, < からなる長さ M の文字列は 3^M 通りありますが、そのうち実験で得られた S として考えられるものは何通りありますか?
答えは非常に大きくなることがあるので、 998244353 で割った余りを出力してください。

制約

  • 入力は全て整数
  • 2 \le N \le 17
  • 1 \le M \le \frac{N \times (N-1)}{2}
  • 1 \le A_i < B_i \le N
  • i \neq j \Rightarrow (A_i,B_i) \neq (A_j,B_j)

入力

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

N M
A_1 B_1
A_2 B_2
\vdots
A_M B_M

出力

答えを整数として出力せよ。

入力例 1

3 3
1 2
1 3
2 3

出力例 1

13

おもりの重さをおもりの番号順に書き並べた数列を w とします。

  • w=(5,5,5) の時 S= ===
  • w=(2,2,3) の時 S= =<<
  • w=(6,8,6) の時 S= <=>
  • w=(9,4,4) の時 S= >>=
  • w=(7,7,3) の時 S= =>>
  • w=(8,1,8) の時 S= >=<
  • w=(5,8,8) の時 S= <<=
  • w=(1,2,3) の時 S= <<<
  • w=(4,9,5) の時 S= <<>
  • w=(5,1,8) の時 S= ><<
  • w=(6,9,2) の時 S= <>>
  • w=(7,1,3) の時 S= >><
  • w=(9,7,5) の時 S= >>>

という文字列 S を得ます。
他にもおもりの重さとして考えられる列は無数にありますが、 S として考えられるのは以上の 13 通りです。

入力例 2

4 4
1 4
2 3
1 3
3 4

出力例 2

39

入力例 3

14 15
1 2
1 3
2 4
2 5
2 6
4 8
5 6
6 8
7 8
9 10
9 12
9 13
10 11
11 12
11 13

出力例 3

1613763

Score : 650 points

Problem Statement

There are N weights numbered 1,2, \dots,N.
Using a balance, we will compare weights M times.

  • Before the comparisons, prepare an empty string S.
  • For the i-th comparison, put just weight A_i to the left bowl, and just weight B_i to the right.
  • Then, one of the following three results is obtained.
    • If weight A_i is heavier than weight B_i,
      • append > to the tail of S.
    • If weight A_i and weight B_i have the same mass,
      • append = to the tail of S.
    • If weight A_i is lighter than weight B_i,
      • append < to the tail of S.
  • The result is always accurate.

After the experiment, you will obtain a string S of length M.
Among the 3^M strings of length M consisting of >, =, and <, how many can be obtained as S by the experiment?
Since the answer can be enormous, print the answer modulo 998244353.

Constraints

  • All input values are integers.
  • 2 \le N \le 17
  • 1 \le M \le \frac{N \times (N-1)}{2}
  • 1 \le A_i < B_i \le N
  • i \neq j \Rightarrow (A_i,B_i) \neq (A_j,B_j)

Input

The input is given from Standard Input in the following format:

N M
A_1 B_1
A_2 B_2
\vdots
A_M B_M

Output

Print the answer as an integer.

Sample Input 1

3 3
1 2
1 3
2 3

Sample Output 1

13

Let w be the sequence of the mass of the weights, in ascending order of weight numbers.

  • If w=(5,5,5), you obtain S= ===.
  • If w=(2,2,3), you obtain S= =<<.
  • If w=(6,8,6), you obtain S= <=>.
  • If w=(9,4,4), you obtain S= >>=.
  • If w=(7,7,3), you obtain S= =>>.
  • If w=(8,1,8), you obtain S= >=<.
  • If w=(5,8,8), you obtain S= <<=.
  • If w=(1,2,3), you obtain S= <<<.
  • If w=(4,9,5), you obtain S= <<>.
  • If w=(5,1,8), you obtain S= ><<.
  • If w=(6,9,2), you obtain S= <>>.
  • If w=(7,1,3), you obtain S= >><.
  • If w=(9,7,5), you obtain S= >>>.

While there is an infinite number of possible sequences of the mass of the weights, S is always one of the 13 above.

Sample Input 2

4 4
1 4
2 3
1 3
3 4

Sample Output 2

39

Sample Input 3

14 15
1 2
1 3
2 4
2 5
2 6
4 8
5 6
6 8
7 8
9 10
9 12
9 13
10 11
11 12
11 13

Sample Output 3

1613763