P6846 [CEOI 2019] Amusement Park

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.

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$.

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$.

#### 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: | Subtask ID | Constraint | Score | | :-: |:-:|:-:| | 1 | $n\le 3$ | $7$ | | 2 | $n\le 6$ | $12$ | | 3 | $n\le 10$ | $23$ | | 4 | $n\le 15$ | $21$ | | 5 | No additional constraints | $37$ | #### Note This problem is translated from [Central-European Olympiad in Informatics 2019](https://ceoi.sk/) [Day 2](https://ceoi.sk/tasks/) [T1 Amusement Park](https://ceoi.sk/static/statements/amusementpark-ENG.pdf)。 Translated by ChatGPT 5