#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5e5 + 51, MOD = 998244353, INV2 = 499122177;
struct Edge {
  int to, prev;
};
Edge ed[MAXN << 1];
int n, tot, from, to, res, c;
int last[MAXN], f[MAXN];
inline int read() {
  register int num = 0, neg = 1;
  register char ch = getchar();
  while (!isdigit(ch) && ch != '-') {
    ch = getchar();
  }
  if (ch == '-') {
    neg = -1;
    ch = getchar();
  }
  while (isdigit(ch)) {
    num = (num << 3) + (num << 1) + (ch - '0');
    ch = getchar();
  }
  return num * neg;
}
inline void addEdge(int from, int to) {
  ed[++tot].prev = last[from];
  ed[tot].to = to;
  last[from] = tot;
}
inline void dfs(int node, int fa) {
  int prod = 1;
  for (register int i = last[node]; i; i = ed[i].prev) {
    if (ed[i].to != fa) {
      dfs(ed[i].to, node),
          prod = (long long int)prod * (1 + f[ed[i].to]) % MOD * INV2 % MOD;
    }
  }
  res = (res + (f[node] = prod == 1 ? 0 : MOD + 1 - prod)) % MOD;
}
int main() {
  n = read(), c = 1;
  for (register int i = 0; i < n - 1; i++) {
    from = read(), to = read(), addEdge(from, to), addEdge(to, from),
    c = (c + c) % MOD;
  }
  dfs(1, 0), printf("%d\n", (long long int)res * (c + c) % MOD);
}

### Prompt

Please create a solution in cpp 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;
const int MAXN = 5e5 + 51, MOD = 998244353, INV2 = 499122177;
struct Edge {
  int to, prev;
};
Edge ed[MAXN << 1];
int n, tot, from, to, res, c;
int last[MAXN], f[MAXN];
inline int read() {
  register int num = 0, neg = 1;
  register char ch = getchar();
  while (!isdigit(ch) && ch != '-') {
    ch = getchar();
  }
  if (ch == '-') {
    neg = -1;
    ch = getchar();
  }
  while (isdigit(ch)) {
    num = (num << 3) + (num << 1) + (ch - '0');
    ch = getchar();
  }
  return num * neg;
}
inline void addEdge(int from, int to) {
  ed[++tot].prev = last[from];
  ed[tot].to = to;
  last[from] = tot;
}
inline void dfs(int node, int fa) {
  int prod = 1;
  for (register int i = last[node]; i; i = ed[i].prev) {
    if (ed[i].to != fa) {
      dfs(ed[i].to, node),
          prod = (long long int)prod * (1 + f[ed[i].to]) % MOD * INV2 % MOD;
    }
  }
  res = (res + (f[node] = prod == 1 ? 0 : MOD + 1 - prod)) % MOD;
}
int main() {
  n = read(), c = 1;
  for (register int i = 0; i < n - 1; i++) {
    from = read(), to = read(), addEdge(from, to), addEdge(to, from),
    c = (c + c) % MOD;
  }
  dfs(1, 0), printf("%d\n", (long long int)res * (c + c) % MOD);
}

```