Problem1206--#6240. 仙人掌

1206: #6240. 仙人掌

Time Limit: 1 Sec  Memory Limit: 986 MB
Submit: 0  Solved: 0
[Submit] [Status] [Web Board] [Creator:]

Description

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

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

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

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

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

请求出 ansansans 的期望,答案模 998244353998244353998244353

输入格式

第一行两个整数 N,MN,MN,M

接下来 MMM 行,每行两个整数 ui,viu_i,v_iui,vi 描述一条边。

输出格式

一行一个整数表示答案。

样例

样例输入

5 4
1 2
1 3
1 4
1 5

样例输出

13

数据范围与提示

对于100%100\%100%的数据,有1≤N≤4001\le N\le 4001N400

有四个子任务:

Subtask 1(30pts30pts30pts):M=N−1M = N - 1M=N1

Subtask 2(20pts20pts20pts):M=NM = NM=N

Subtask 3(20pts20pts20pts):N≤15N\le 15N15

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

Source/Category