#6240. 仙人掌

内存限制:986 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: wxh010910

题目描述

如果一个无自环无重边无向连通图的任意一条边最多属于一个简单环,我们就称之为仙人掌。所谓简单环即不经过重复的结点的环。

现在给你一个 N 个点, M 条边的仙人掌,你想要求出对其点分治的期望复杂度,点分治过程如下:

  • ans 加上当前连通块大小。

  • 从当前连通块中随机选择一个点,将其删除,并删除它连出去的所有边。

  • 对剩下的每个连通块递归调用这个函数。

请求出 ans 的期望,答案模 998244353

输入格式

第一行两个整数 N,M

接下来 M 行,每行两个整数 u_i,v_i 描述一条边。

输出格式

一行一个整数表示答案。

样例

样例输入

5 4
1 2
1 3
1 4
1 5

样例输出

13

数据范围与提示

对于 100\% 的数据,有 1\le N\le 400

有四个子任务:

Subtask 1( 30pts ): M = N - 1

Subtask 2( 20pts ): M = N

Subtask 3( 20pts ): N\le 15

Subtask 4( 30pts ):无其他限制。