小时候的你听说,如果在滑稽树丰收的时候,手牵着手吃下滑稽果,那么就可以心意相通,永世不离。于是兴奋的你带上了小书包,在滑稽树下等着熟透的滑稽果落下。
这天,你一共捡到了 $n$ 颗滑稽果,其中第 $i$ 颗滑稽果的价值是 $w_i$。然而你的小书包实在是太小了,只能装下一颗滑稽果或者两颗形状比较契合的滑稽果。
经过一番尝试,你发现了只有 $m$ 对滑稽果 $(a_i,b_i)$ 可以被同时放进书包中。于是你轻易地找到了价值和最大的组合,并和青梅竹马的她度过了一个浪漫的夜晚。
虽然时光渐渐地逝去,但是童年时的浪漫一直埋藏在你们的心里。现在,你和你的她打算在明天——一年一度滑稽树收获的日子,在滑稽树下回忆儿时的美好。
在出发之前,你想起了你的小书包以及那些滑稽果。虽然你仍然记得哪 $m$ 对滑稽果是契合的,但是每一个滑稽果的价格却是无论如何也回忆不起来了。于是你打算简单的估计一下当时带回去的滑稽果的价值和:你假设每个滑稽果的价值都是 $[0,1]$ 之间的均匀随机变量,且都是独立的,你想要计算带回去的滑稽果价值的期望。
下面形式化地给出题意:$x_1,x_2,...,x_n$ 为 $n$ 个独立随机变量,且均服从 $[0,1]$ 上的均匀分布。给出 $m$ 对关系 $(a_i,b_i)$,令 $f(x) = \max(\max_{i=1}^nx_i,\max_{i=1}^m(x_{a_i}+x_{b_i}))$,求 $f(x)$ 的期望。
输入格式
第一行两个正整数 $n,m$,表示滑稽果的数量与形状契合的对数。
接下来 $m$ 行每行两个整数 $a_i,b_i(1 \leq a_i < b_i \leq n)$,表示一对契合的滑稽果。
输出格式
一行一个整数表示答案,模 $998244353$($7 \times 17 \times 2^{23} + 1$,一个质数)后输出。即如果答案可以表示为最简分数 $\frac{x}{y}$ 的形式,你需要输出 $x \times y^{-1} \mod 998244353$。
样例一
input
3 2 1 2 2 3
output
166374060
explanation
不难发现答案一定是 $\max(x_1,x_3)+x_2$,其中 $\max(x_1,x_3)$ 的期望是 $\frac{2}{3}$,$x_2$ 的期望是 $\frac{1}{2}$,所以 $f(x)$ 的期望是 $\frac{7}{6}$,在模 $998244353$ 意义下是 $166374060$。
样例二
input
5 0
output
831870295
explanation
答案是 $\max_{i=1}^n x_i$,即 $\frac{5}{6}$,在模 $998244353$ 意义下是 $831870295$。
样例三
input
5 7 1 2 2 3 3 4 4 5 1 3 3 5 2 4
output
776412276
样例四
见样例数据下载,$n = 10$,满足性质二(见限制与约定)。
样例五
见样例数据下载,$n = 10$。
限制与约定
由于一些原因,本题使用捆绑测试。每个子任务有若干个测试点,分为 $5$ 个子任务,你只有通过一个子任务的所有测试点才能得到这个子任务的分数。
子任务 | 分值 | $n$ 的规模 | 其他 |
---|---|---|---|
1 | $10$ | $n \leq 25$ | 满足性质一 |
2 | $20$ | 满足性质二 | |
3 | $20$ | $n \leq 4$ | 无 |
4 | $20$ | $n \leq 10$ | |
5 | $20$ | $n \leq 15$ | |
6 | $10$ | $n \leq 25$ |
性质一:$m = n -1$,且 $a_i = 1$。
性质二:如果将滑稽果看做点,契合关系看做边,那么得到的图是一棵树。
对于 $100\%$ 的数据,$n \geq 1, 0 \leq m \leq \frac{n(n-1)}{2}$,保证不会有任何两对契合关系相同。
时间限制:$2\texttt{s}$
空间限制:$256\texttt{MB}$