2540. 「PKUWC2018」随机算法

时间限制：1000 ms
内存限制：512 MiB
通过次数：617
提交次数：1109

题目描述

我们知道，求任意图的最大独立集是一类 NP 完全问题，目前还没有准确的多项式算法，但是有许多多项式复杂度的近似算法。

例如，小 C 常用的一种算法是：

对于一个有 $n$ 个点的无向图，先等概率随机一个 $1 \ldots n$ 的排列 $p[1 \ldots n]$ 。

维护答案集合 $S$ ，一开始 $S$ 为空集，之后按照 $i=1 \ldots n$ 的顺序，检查 $\{p[i]\} \cup S$ 是否是一个独立集，如果是的话就令 $S = \{p[i]\} \cup S$ 。

最后得到一个独立集 $S$ 作为答案。

小 C 现在想知道，对于给定的一张图，这个算法的正确率，输出答案对 $998244353$ 取模。

第一行两个非负整数 $n, m$ 表示给定的图的点数和边数。

接下来 $m$ 行，每行有两个正整数 $(u, v)$ ( $u \neq v$ ) 描述这张图的一条无向边。

输出正确率，答案对 $998244353$ 取模。

输入

3 2
1 2
2 3

输出

665496236

样例解释

这张图的最大独立集显然为 $2$ ，可以发现只有 $p[1] = 2$ 时会得出 $S = \{2\}$ ，否则都是 $S = \{1,3\}$ ，所以答案是 $\frac{2}{3}$ 。

对于 $10\%$ 的数据，有 $1 \leq n \leq 9$ 。
对于 $30\%$ 的数据，有 $1 \leq n \leq 13$ 。
对于 $50\%$ 的数据，有 $1 \leq n \leq 17$ 。
另有 $10\%$ 的数据，满足给定的图是一条链。
另有 $10\%$ 的数据，满足给定的图是一棵树。
对于 $100\%$ 的数据，有 $1 \leq n \leq 20$ ， $0 \leq m \leq \frac{n \times (n-1)}{2}$ ，保证给定的图没有重边和自环。