Description

We know that finding the maximum independent set of an arbitrary graph is an NP-complete problem. Currently, there is no exact polynomial-time algorithm, but there are many polynomial-time approximation algorithms.

For example, one algorithm often used by Little C is:

1. For an undirected graph with $n$ vertices, first uniformly randomly generate a permutation $p[1\ldots n]$ of $1\ldots n$.

2. Maintain an answer set $S$. Initially, $S$ is empty. Then, in the order $i=1\ldots n$, check whether $\{p[i]\}\cup S$ is an independent set. If it is, set $S=\{p[i]\}\cup S$.

3. Finally, obtain an independent set $S$ as the answer.

Now Little C wants to know, for a given graph, the probability that this algorithm is correct. Output the answer modulo $998244353$.

Input Format

The first line contains two non-negative integers $n,m$, representing the number of vertices and edges of the given graph.

The next $m$ lines each contain two positive integers $(u,v)$ $(u\neq v)$, describing an undirected edge of the graph.

Output Format

Output the probability of being correct, modulo $998244353$.

3 2
1 2
2 3

665496236

Hint

Sample Explanation

The maximum independent set size of this graph is clearly $2$. It can be seen that only when $p[1]=2$ will we get $S=\{2\}$; otherwise, we always get $S=\{1,3\}$. Therefore, the answer is $\frac{2}{3}$.

Constraints

For $10\%$ of the testdata, $1\leq n\leq 9$.

For $30\%$ of the testdata, $1\leq n\leq 13$.

For $50\%$ of the testdata, $1\leq n\leq 17$.

Another $10\%$ of the testdata satisfies that the given graph is a path.

Another $10\%$ of the testdata satisfies that the given graph is a tree.

For $100\%$ of the testdata, $1\leq n\leq 20$, $0\leq m\leq \frac{n\times (n-1)}{2}$. It is guaranteed that the given graph has no multiple edges and no self-loops.

Translated by ChatGPT 5