#P5492. [PKUWC2018] 随机算法

[PKUWC2018] 随机算法

题目描述

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

例如,小 C 常用的一种算法是:

  1. 对于一个 nn 个点的无向图,先等概率随机一个 1n1\ldots n 的排列 p[1n]p[1\ldots n]

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

  3. 最后得到一个独立集 SS 作为答案。

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

输入格式

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

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

输出格式

输出正确率,答案对 998244353998244353 取模。

3 2
1 2
2 3
665496236

提示

样例解释

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

数据范围

对于 10%10\% 的数据,有1n91\leq n\leq 9

对于 30%30\% 的数据,有1n131\leq n\leq 13

对于 50%50\% 的数据,有1n171\leq n\leq 17

另有 10%10\% 的数据,满足给定的图是一条链。

另有 10%10\% 的数据,满足给定的图是一棵树。

对于 100%100\% 的数据,有1n201\leq n\leq 200mn×(n1)20\leq m\leq \frac{n\times (n-1)}{2},保证给定的图没有重边和自环。