题目描述

对于一棵无向树 $t$，定义有理数 $f(t)$ 如下：

• 设 $t$ 的顶点数为 $n$。
• 当 $n=1$ 时：$f(t)=1$。
• 当 $n \geq 2$ 时：
  • 对于 $t$ 的每一条边 $e$，将 $e$ 从 $t$ 中删除后得到的两棵树分别记为 $t_x(e), t_y(e)$（顺序无关）。
  • $f(t) = \left( \sum\_{e \in t} f(t\_x(e)) \times f(t\_y(e)) \right) / n$。

给定一棵有 $N$ 个顶点、顶点编号为 $1$ 到 $N$ 的树 $T$。第 $i$ 条边连接顶点 $A_i$ 和顶点 $B_i$。

请计算 $f(T)$ 的值，并对 $998244353$ 取模。

有理数 $\bmod\ 998244353$ 的定义：在本题的约束下，设所求有理数为最简分数 $\frac{P}{Q}$，可以证明 $Q \not\equiv 0 \pmod{998244353}$。因此，存在唯一的整数 $R$ 满足 $R \times Q \equiv P \pmod{998244353},\ 0 \leq R < 998244353$。请输出这个 $R$。

输入格式

输入按以下格式从标准输入给出：

$N$
$A_1$ $B_1$
$A_2$ $B_2$
$\vdots$
$A_{N-1}$ $B_{N-1}$

输出格式

请输出答案。

样例 1

输入

2
1 2

输出

499122177

样例 2

输入

3
1 2
2 3

输出

332748118

样例 3

输入

4
1 2
2 3
3 4

输出

103983787

样例 4

输入

10
4 5
1 9
6 1
8 4
5 9
4 7
3 10
5 2
4 3

输出

462781191

说明/提示

限制

• $2 \leq N \leq 5000$
• $1 \leq A_i, B_i \leq N$
• 输入的图保证是一棵树

样例解释 1

$f(T) = 1/2$。

样例解释 2

$f(T) = 1/3$。

由 ChatGPT 4.1 翻译