Score : $650$ points

问题描述

有 $N$ 个编号为 $1,2, \dots,N$ 的砝码。
我们将使用天平进行 $M$ 次砝码比较。

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

实验结束后，你会得到一个长度为 $M$ 的字符串 $S$。
在由 >, =, < 组成的长度为 $M$ 的所有 $3^M$ 个字符串中，有多少个可以通过该实验获得作为 $S$？
由于答案可能非常大，请输出答案对 $998244353$ 取模的结果。

以上为通义千问 qwen-max 翻译，仅供参考。

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

update @ 2024/3/10 08:40:17