AT_abc306_h [ABC306Ex] Balance Scale

题目描述

有 $N$ 个编号为 $1,2,\dots,N$ 的砝码。
接下来你将用天平进行 $M$ 次重量比较。

• 在比较开始前，准备一个空字符串 $S$。
• 第 $i$ 次比较时，将砝码 $A_i$ 放在天平左盘，将砝码 $B_i$ 放在右盘。
• 此时会得到以下三种结果之一：
  • 砝码 $A_i$ 比砝码 $B_i$ 重。
    • 此时在 $S$ 的末尾添加 >。
  • 砝码 $A_i$ 和砝码 $B_i$ 重量相同。
    • 此时在 $S$ 的末尾添加 =。
  • 砝码 $B_i$ 比砝码 $A_i$ 重。
    • 此时在 $S$ 的末尾添加 <。
• 天平不会给出错误的结果。

实验结束后，你会得到一个长度为 $M$ 的字符串 $S$。
由 >、=、< 组成的长度为 $M$ 的字符串共有 $3^M$ 种，但作为实验结果可能出现的 $S$ 有多少种？
由于答案可能非常大，请输出其对 $998244353$ 取模的结果。

输入格式

输入以如下格式从标准输入读入。

$N\ M$

$A_1\ B_1$

$A_2\ B_2$

$\vdots$

$A_M\ B_M$

输出格式

请输出答案的整数值。

输入输出样例 #1

输入 #1

3 3
1 2
1 3
2 3

输出 #1

13

输入输出样例 #2

输入 #2

4 4
1 4
2 3
1 3
3 4

输出 #2

39

输入输出样例 #3

输入 #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

说明/提示

限制条件

• 所有输入均为整数。
• $2 \leq N \leq 17$
• $1 \leq M \leq \frac{N \times (N-1)}{2}$
• $1 \leq A_i < B_i \leq N$
• $i \neq j \Rightarrow (A_i,B_i) \neq (A_j,B_j)$

样例解释 1

将砝码的重量按编号顺序排列成数列 $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$ 种。

由 ChatGPT 4.1 翻译，123asdf123 修缮。