#AT2612. Ex - Balance Scale

Ex - Balance Scale

当前没有测试数据。

Ex - Balance Scale

Score : $650$ points

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:

NN MM

A1A_1 B1B_1

A2A_2 B2B_2

\vdots

AMA_M BMB_M

Output

Print the answer as an integer.


3 3
1 2
1 3
2 3
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.


4 4
1 4
2 3
1 3
3 4
39

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
1613763