Description

There is a directed graph with $n$ vertices and $m$ edges. The graph has no multiple edges and no self-loops, and there is no cycle between any two vertices.

Now we want to reverse the direction of some edges so that the directed graph becomes acyclic.

You need to compute the answer after taking $\bmod\ 998244353$: for every valid way of reversing edges that makes the graph acyclic, take the number of edges that are reversed in this way; sum these numbers over all valid ways.

Input Format

The first line contains two integers $n, m$.

The next $m$ lines each contain two integers $a_i, b_i$, meaning there is a directed edge that starts at $a_i$ and ends at $b_i$.

Output Format

Print one integer: the sum, over every way of reversing edges that makes the graph acyclic, of the number of edges that must be reversed, taken $\bmod\ 998244353$.

2 1
1 2

1

3 3
1 2
2 3
1 3

9

Hint

Sample Explanation

Sample 1 Explanation

There are two possible ways:

• Reverse the direction.
• Do not reverse the direction.

So the output is $1+0=1$.

Sample 2 Explanation

There are six feasible ways:

• $1\to2,2\to3,1\to3$
• $1\to2,3\to2,1\to3$
• $1\to2,3\to2,3\to1$
• $2\to1,2\to3,1\to3$
• $2\to1,2\to3,3\to1$
• $2\to1,3\to2,3\to1$

So the output is $0+1+2+1+2+3=9$.

Constraints

For $100\%$ of the testdata, it is guaranteed that $1\le n\le 18$, $0\le m\le \frac{n\times (n-1)}{2}$, $1\le a_i,b_i\le n$, $a_i\not=b_i$, for $i\not=j$ we have $a_i\not=a_j$ or $b_i\not=b_j$, and the unordered pairs $\{a_i,b_i\}$ are all distinct.

The detailed subtask constraints and scores are as follows:

Note

This problem is translated from Central-European Olympiad in Informatics 2019 Day 2 T1 Amusement Park。

Translated by ChatGPT 5