#P1067E. Random Forest Rank

    ID: 4469 Type: RemoteJudge 3000ms 512MiB Tried: 0 Accepted: 0 Difficulty: (None) Uploaded By: Tags>dpgraph matchingsmathtrees*2800

Random Forest Rank

No submission language available for this problem.

Description

Let's define rank of undirected graph as rank of its adjacency matrix in $\mathbb{R}^{n \times n}$.

Given a tree. Each edge of this tree will be deleted with probability $1/2$, all these deletions are independent. Let $E$ be the expected rank of resulting forest. Find $E \cdot 2^{n-1}$ modulo $998244353$ (it is easy to show that $E \cdot 2^{n-1}$ is an integer).

First line of input contains $n$ ($1 \le n \le 5 \cdot 10^{5}$) — number of vertices.

Next $n-1$ lines contains two integers $u$ $v$ ($1 \le u, \,\, v \le n; \,\, u \ne v$) — indices of vertices connected by edge.

It is guaranteed that given graph is a tree.

Print one integer — answer to the problem.

Input

First line of input contains $n$ ($1 \le n \le 5 \cdot 10^{5}$) — number of vertices.

Next $n-1$ lines contains two integers $u$ $v$ ($1 \le u, \,\, v \le n; \,\, u \ne v$) — indices of vertices connected by edge.

It is guaranteed that given graph is a tree.

Output

Print one integer — answer to the problem.

Samples

3
1 2
2 3

6

4
1 2
1 3
1 4

14

4
1 2
2 3
3 4

18