让我们将无向图的秩定义为其邻接矩阵在 $$$\mathbb{R}^{n \times n}$$$ 中的秩。
给定一棵树。这棵树的每条边都会以 $$$1/2$$$ 的概率被删除,所有这些删除都是独立的。令 $$$E$$$ 为结果森林的预期排名。求 $$$E \cdot 2^{n-1}$$$ 对 $$$998244353$$$ 取模(很容易证明 $$$E \cdot 2^{n-1}$$$ 是一个整数)。
输入
输入的第一行包含 $$$n$$$ ($$$1 \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