#P13469. [ABC306Ex] Balance Scale

    ID: 12653 传统题 3000ms 1024MiB 尝试: 2 已通过: 2 难度: 8 上传者: 标签>CF2400状压DP组合数学图论并查集动态规划字符串

[ABC306Ex] Balance Scale

AT_abc306_h [ABC306Ex] Balance Scale

时间限制3.00s 内存限制1.00GB

题目描述

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

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

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

输入格式

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

N MN\ M

A1 B1A_1\ B_1

A2 B2A_2\ B_2

⋮\vdots

AM BMA_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≤N≤172 \leq N \leq 17
  • 1≤M≤N×(N−1)21 \leq M \leq \frac{N \times (N-1)}{2}
  • 1≤Ai<Bi≤N1 \leq A_i < B_i \leq N
  • i≠j⇒(Ai,Bi)≠(Aj,Bj)i \neq j \Rightarrow (A_i,B_i) \neq (A_j,B_j)

样例解释 1

将砝码的重量按编号顺序排列成数列 ww。

  • 当 w=(5,5,5)w=(5,5,5) 时,S=S= ===。
  • 当 w=(2,2,3)w=(2,2,3) 时,S=S= =<<。
  • 当 w=(6,8,6)w=(6,8,6) 时,S=S= <=>。
  • 当 w=(9,4,4)w=(9,4,4) 时,S=S= >>=。
  • 当 w=(7,7,3)w=(7,7,3) 时,S=S= =>>。
  • 当 w=(8,1,8)w=(8,1,8) 时,S=S= >=<。
  • 当 w=(5,8,8)w=(5,8,8) 时,S=S= <<=。
  • 当 w=(1,2,3)w=(1,2,3) 时,S=S= <<<。
  • 当 w=(4,9,5)w=(4,9,5) 时,S=S= <<>。
  • 当 w=(5,1,8)w=(5,1,8) 时,S=S= ><<。
  • 当 w=(6,9,2)w=(6,9,2) 时,S=S= <>>。
  • 当 w=(7,1,3)w=(7,1,3) 时,S=S= >><。
  • 当 w=(9,7,5)w=(9,7,5) 时,S=S= >>>。

除此之外,砝码重量的排列方式有无数种,但作为 SS 可能出现的情况只有上述 1313 种。