如果一个无自环无重边无向连通图的任意一条边最多属于一个简单环,我们就称之为仙人掌。所谓简单环即不经过重复的结点的环。
现在给你一个 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 4001≤N≤400。
有四个子任务:
Subtask 1(30pts30pts30pts):M=N−1M = N - 1M=N−1。
Subtask 2(20pts20pts20pts):M=NM = NM=N。
Subtask 3(20pts20pts20pts):N≤15N\le 15N≤15。
Subtask 4(30pts30pts30pts):无其他限制。