← 返回题目列表

AtCoder · abc306_h

Ex. 天平秤

中文机器翻译题面 查看原题

分数: 650 点

问题陈述

有 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.
  • 结果始终准确。

实验结束后,你会得到一个字符串 S 长度 M.
其中 3^M 长度的字符串 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 是重量的质量序列,按重量编号的升序排列。

  • If w=(5,5,5),您获得 S= ===.
  • If w=(2,2,3),您获得 S= =<<.
  • If w=(6,8,6),您获得 S= <=>.
  • If w=(9,4,4),您获得 S= >>=.
  • If w=(7,7,3),您获得 S= =>>.
  • If w=(8,1,8),您获得 S= >=<.
  • If w=(5,8,8),您获得 S= <<=.
  • If w=(1,2,3),您获得 S= <<<.
  • If w=(4,9,5),您获得 S= <<>.
  • If w=(5,1,8),您获得 S= ><<.
  • If w=(6,9,2),您获得 S= <>>.
  • If w=(7,1,3),您获得 S= >><.
  • If 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