可怜有一棵 $n$ 个点的树, 定义树上两个点 $a,b$ 的距离 $dis(a,b)$ 为树上从 $a$ 走到 $b$ 最少需要多少条边.
可怜想要先选择 $k$ 条树边把他们删掉, 然后再添加 $k$ 条边使得结果仍然还是一棵树.
现在他想知道的是, 对于所有可以选择的合法方案(也就是操作完后仍然是一棵树), $\sum_{i=1}^{n}\sum_{j=i+1}^{n}dis(i,j)$ 的和.
由于答案可能很大, 你只需要输出答案对 $998244353$ 取模后的值.
输入格式
第一行两个整数 $n,k$.
接下来 $n-1$ 行, 第 $i$ 行两个正整数 $(u_i,v_i)$ 描述一条树边.
输出格式
输出答案对 $998244353$ 取模后的值.
样例数据
样例 1 输入
3 1 1 2 2 3
样例 1 输出
16
子任务
对于所有数据, 保证 $3\leq n\leq 10^5$ , $0\leq k\leq 1$. 且读入的一定是一棵树.
Task1(9pts):保证 $n\leq 10$.
Task2(13pts):保证 $n\leq 100$.
Task3(11pts):保证 $n\leq 1000$.
Task4(10pts):保证 $k=0$.
Task5(17pts):保证 $u_i=i,v_i=i+1$.
Task6(40pts):无限制.