markdown

E. 随机森林的秩

每个测试的时间限制：$3$ 秒
每个测试的内存限制：$512$ MB
输入：标准输入
输出：标准输出

定义无向图的秩为其 $n \times n$ 邻接矩阵的秩。

给定一棵树。树中的每条边以 $\frac{1}{2}$ 的概率被删除，且所有删除操作相互独立。设 $E$ 为最终得到的森林的期望秩。请计算 $E \cdot 2^{n-1}$ 对 $998244353$ 取模的结果（可以证明 $E \cdot 2^{n-1}$ 是一个整数）。

输入

第一行包含一个整数 $n$（$2 \le n \le 5 \cdot 10^5$）—— 树的顶点数。
接下来 $n-1$ 行，每行包含两个整数 $u, v$（$1 \le u, v \le n$；$u \ne v$）—— 一条边连接的两个顶点编号。
输入保证给定的图是一棵树。

输出

输出一个整数 —— 问题的答案。

样例

输入示例 1

3
1 2
2 3

输出示例 1

6

输入示例 2

4
1 2
1 3
1 4

输出示例 2

14

输入示例 3

4
1 2
2 3
3 4

输出示例 3

18