#3070. 「2019 集训队互测 Day 1」最短路径

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

题目描述

小 E 和小 F 在做游戏。他们找来了一个无向连通图 G=(V,E) 。图 G 满足 V=\{1,2,\dots,n\} |E|=n

定义 d(u,v)=G u v 之间的最短距离,这里 G 中的每条边权值均为 1 。小 E 会在所有满足 u,v\in V ,且 u< v 的点对 (u,v) 中随机选择一个,然后让小 F 求出 d(u,v)^k ,作为这次游戏的快乐程度。

在游戏之前,小 F 想知道游戏的快乐程度的期望,于是让小 O 去算。小 O 不会算,找到了你。

输入格式

第一行包含两个整数 n,k

接下来 n 行每行两个整数 u,v 表示 (u,v)\in E

输出格式

设答案为 p\over q ,且 \gcd(p,q)=1 ,则应该输出一个整数 r 满足 q\cdot r\equiv p \bmod 998244353,0\le r<998244353 ,可以证明在本题中 r 是唯一的。

样例

样例输入

4 3
1 2
2 3
3 4
2 4

样例输出

332748121

样例说明

d(1,2)=d(2,3)=d(3,4)=d(2,4)=1 d(1,3)=d(1,4)=2

数据范围与提示

本题采用子任务制。对于所有数据满足 1\le n\le 10^5,1\le k\le 10^9 ,保证给定的图 G 满足题中要求,且不存在重边。

\texttt{subtask 1:}~ 5\% ,满足 n\le 1000

\texttt{subtask 2:}~10\% ,满足 k=1

\texttt{subtask 3:}~15\% ,满足 k=2

\texttt{subtask 4:}~30\% ,满足 G 中存在一条边 (u,u)

\texttt{subtask 5:}~40\% ,无额外限制。