题目描述
如果一个无自环无重边无向连通图的任意一条边最多属于一个简单环,我们就称之为仙人掌。所谓简单环即不经过重复的结点的环。
现在给一你一棵 $N$ 个点 $M$ 条边的仙人掌,小 $D$ 在上面运行一个随机点分治算法:
将图的大小累加到全局变量 $ans$ 上;
随机图中一个点,删除该点及其所有出边;
对新产生的每个连通块递归调用该算法。
请求出 $ans$ 的期望;答案模 $998244353$.
保证答案可以写成 $p/q$ 的形式,其中 $(p, q) = 1$ 且 $q$ 不是 $998244353$ 的倍数。你只需要输出 $p\times q^{998244351} (\mod 998244353)$.
输入格式
第一行两个整数 $N, M$ 。 接下来 $M$ 行,每行两个整数 $u_i , v_i$ 描述一条边。
输出格式
一行一个整数表示答案。
样例输入
5 4
1 2
1 3
1 4
1 5
样例输出
13
数据范围
对所有数据,$保证 1 ≤ N ≤ 400$.
$M = N − 1$ ( 16 分)
$M = N$ ( 18 分)
$N ≤ 15$ ( 15 分)
没有特殊性质( 51 分)
