#include <bits/stdc++.h>
using namespace std;
int Read() {
  int X = 0, flag = 1;
  char ch = 0;
  while (ch < '0' || ch > '9') {
    if (ch == '-') flag = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9')
    X = (X << 1) + (X << 3) + ch - 48, ch = getchar();
  return X * flag;
}
void Write(int x) {
  if (x < 0) x = -x, putchar('-');
  if (x > 9) Write(x / 10);
  putchar(x % 10 + 48);
}
int n;
int edgenum, Edge[500005 << 1], nxt[500005 << 1], head[500005];
inline void addedge(int x, int y) {
  Edge[++edgenum] = y;
  nxt[edgenum] = head[x];
  head[x] = edgenum;
}
int dp[500005];
void dfs(int now, int fa) {
  int prod = 1;
  for (int i = head[now]; i; i = nxt[i]) {
    int tmp = Edge[i];
    if (tmp == fa) continue;
    dfs(tmp, now);
    prod = (long long)prod * (dp[tmp] + 1) % 998244353 * 499122177 % 998244353;
  }
  dp[now] = (1 - prod + 998244353) % 998244353;
}
int main() {
  n = Read();
  for (int i = 1; i < n; i++) {
    int x = Read(), y = Read();
    addedge(x, y);
    addedge(y, x);
  }
  dfs(1, 0);
  int ans = 0;
  for (int i = 1; i <= n; i++) ans = (ans + dp[i]) % 998244353;
  for (int i = 1; i < n; i++) ans = ans * 2 % 998244353;
  ans = ans * 2 % 998244353;
  Write(ans);
  (putchar('\n'));
  return 0;
}

### Prompt

Generate a Cpp solution to the following problem:

Let's define rank of undirected graph as rank of its adjacency matrix in R^{n × 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 ⋅ 2^{n-1} modulo 998244353 (it is easy to show that E ⋅ 2^{n-1} is an integer).

Input

First line of input contains n (1 ≤ n ≤ 5 ⋅ 10^{5}) — number of vertices.

Next n-1 lines contains two integers u v (1 ≤ u,    v ≤ n;    u ≠ v) — indices of vertices connected by edge.

It is guaranteed that given graph is a tree.

Output

Print one integer — answer to the problem.

Examples

Input

3
1 2
2 3


Output

6


Input

4
1 2
1 3
1 4


Output

14


Input

4
1 2
2 3
3 4


Output

18

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
int Read() {
  int X = 0, flag = 1;
  char ch = 0;
  while (ch < '0' || ch > '9') {
    if (ch == '-') flag = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9')
    X = (X << 1) + (X << 3) + ch - 48, ch = getchar();
  return X * flag;
}
void Write(int x) {
  if (x < 0) x = -x, putchar('-');
  if (x > 9) Write(x / 10);
  putchar(x % 10 + 48);
}
int n;
int edgenum, Edge[500005 << 1], nxt[500005 << 1], head[500005];
inline void addedge(int x, int y) {
  Edge[++edgenum] = y;
  nxt[edgenum] = head[x];
  head[x] = edgenum;
}
int dp[500005];
void dfs(int now, int fa) {
  int prod = 1;
  for (int i = head[now]; i; i = nxt[i]) {
    int tmp = Edge[i];
    if (tmp == fa) continue;
    dfs(tmp, now);
    prod = (long long)prod * (dp[tmp] + 1) % 998244353 * 499122177 % 998244353;
  }
  dp[now] = (1 - prod + 998244353) % 998244353;
}
int main() {
  n = Read();
  for (int i = 1; i < n; i++) {
    int x = Read(), y = Read();
    addedge(x, y);
    addedge(y, x);
  }
  dfs(1, 0);
  int ans = 0;
  for (int i = 1; i <= n; i++) ans = (ans + dp[i]) % 998244353;
  for (int i = 1; i < n; i++) ans = ans * 2 % 998244353;
  ans = ans * 2 % 998244353;
  Write(ans);
  (putchar('\n'));
  return 0;
}

```