103067: [Atcoder]ABC306 Ex - Balance Scale

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

问题描述

有$N$个编号为$1,2,\dots,N$的砝码。

• 在比较之前，准备一个空字符串$S$。
• 对于第$i$次比较，将砝码$A_i$放在左边的碗里，将砝码$B_i$放在右边的碗里。
• 然后，将得到以下三个结果之一。
  • 如果砝码$A_i$比砝码$B_i$重，
    • 将>追加到$S$的末尾。
  • 如果砝码$A_i$和砝码$B_i$的质量相同，
    • 将=追加到$S$的末尾。
  • 如果砝码$A_i$比砝码$B_i$轻，
    • 将<追加到$S$的末尾。
• 结果总是准确的。

实验结束后，你会得到一个长度为$M$的字符串$S$。
在由>、=和<组成的长度为$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$总是上述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