#PQJ311x8454. QOJ 311_8454

    ID: 2907 传统题 2500ms 512MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:集训队赛事:IOI 2019 互测最短路径

QOJ 311_8454

标题: 最短路径 - Problem - QOJ.ac

Statistics

The problem was used in the following contests:

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

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

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

输入格式

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

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

输出格式

设答案为 pq,且 gcd(p,q)=1,则应该输出一个整数 r 满足 q⋅r≡pmod998244353,0≤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≤n≤105,1≤k≤109,保证给定的图 G 满足题中要求,且不存在重边。

subtask 1: 5%,满足 n≤1000 。

subtask 2: 10%,满足 k=1 。

subtask 3: 15%,满足 k=2 。

subtask 4: 30%,满足 G 中存在一条边 (u,u) 。

subtask 5: 40%,无额外限制。