#include <bits/stdc++.h>
using namespace std;
using cat = long long;
cat mod = 998244353;
void DFS(int R, int par, vector<vector<int> >& G, vector<vector<cat> >& cnt,
         vector<vector<cat> >& sum) {
  cat cnt_cur[] = {0, 1};
  cat sum_cur[] = {0, 0};
  cat cnt_cur_nw[2], sum_cur_nw[2];
  for (auto it = G[R].begin(); it != G[R].end(); it++)
    if (*it != par) {
      DFS(*it, R, G, cnt, sum);
      cnt_cur_nw[1] = (2 * cnt[*it][0] + cnt[*it][1]) * cnt_cur[1] % mod;
      sum_cur_nw[1] = ((2 * sum[*it][0] + sum[*it][1]) * cnt_cur[1] +
                       (2 * cnt[*it][0] + cnt[*it][1]) * sum_cur[1]) %
                      mod;
      cnt_cur_nw[0] = (2 * (cnt[*it][0] + cnt[*it][1]) * cnt_cur[0] +
                       cnt[*it][1] * cnt_cur[1]) %
                      mod;
      sum_cur_nw[0] = (2 * (sum[*it][0] + sum[*it][1]) * cnt_cur[0] +
                       2 * (cnt[*it][0] + cnt[*it][1]) * sum_cur[0] +
                       sum[*it][1] * cnt_cur[1] + cnt[*it][1] * sum_cur[1] +
                       cnt[*it][1] * cnt_cur[1]) %
                      mod;
      for (int k = 0; k < 2; k++) {
        cnt_cur[k] = cnt_cur_nw[k];
        sum_cur[k] = sum_cur_nw[k];
      }
    }
  for (int k = 0; k < 2; k++) {
    cnt[R][k] = cnt_cur[k];
    sum[R][k] = sum_cur[k];
  }
}
int main() {
  cin.sync_with_stdio(0);
  cin.tie(0);
  cout << fixed << setprecision(10);
  int N;
  cin >> N;
  vector<vector<int> > G(N);
  for (int i = 0; i < N - 1; i++) {
    int u, v;
    cin >> u >> v;
    G[--u].push_back(--v);
    G[v].push_back(u);
  }
  vector<vector<cat> > cnt(N, vector<cat>(2, 0)), sum(N, vector<cat>(2, 0));
  DFS(0, 0, G, cnt, sum);
  cout << (2 * sum[0][0] + 2 * sum[0][1]) % mod << "\n";
  return 0;
}

### 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;
using cat = long long;
cat mod = 998244353;
void DFS(int R, int par, vector<vector<int> >& G, vector<vector<cat> >& cnt,
         vector<vector<cat> >& sum) {
  cat cnt_cur[] = {0, 1};
  cat sum_cur[] = {0, 0};
  cat cnt_cur_nw[2], sum_cur_nw[2];
  for (auto it = G[R].begin(); it != G[R].end(); it++)
    if (*it != par) {
      DFS(*it, R, G, cnt, sum);
      cnt_cur_nw[1] = (2 * cnt[*it][0] + cnt[*it][1]) * cnt_cur[1] % mod;
      sum_cur_nw[1] = ((2 * sum[*it][0] + sum[*it][1]) * cnt_cur[1] +
                       (2 * cnt[*it][0] + cnt[*it][1]) * sum_cur[1]) %
                      mod;
      cnt_cur_nw[0] = (2 * (cnt[*it][0] + cnt[*it][1]) * cnt_cur[0] +
                       cnt[*it][1] * cnt_cur[1]) %
                      mod;
      sum_cur_nw[0] = (2 * (sum[*it][0] + sum[*it][1]) * cnt_cur[0] +
                       2 * (cnt[*it][0] + cnt[*it][1]) * sum_cur[0] +
                       sum[*it][1] * cnt_cur[1] + cnt[*it][1] * sum_cur[1] +
                       cnt[*it][1] * cnt_cur[1]) %
                      mod;
      for (int k = 0; k < 2; k++) {
        cnt_cur[k] = cnt_cur_nw[k];
        sum_cur[k] = sum_cur_nw[k];
      }
    }
  for (int k = 0; k < 2; k++) {
    cnt[R][k] = cnt_cur[k];
    sum[R][k] = sum_cur[k];
  }
}
int main() {
  cin.sync_with_stdio(0);
  cin.tie(0);
  cout << fixed << setprecision(10);
  int N;
  cin >> N;
  vector<vector<int> > G(N);
  for (int i = 0; i < N - 1; i++) {
    int u, v;
    cin >> u >> v;
    G[--u].push_back(--v);
    G[v].push_back(u);
  }
  vector<vector<cat> > cnt(N, vector<cat>(2, 0)), sum(N, vector<cat>(2, 0));
  DFS(0, 0, G, cnt, sum);
  cout << (2 * sum[0][0] + 2 * sum[0][1]) % mod << "\n";
  return 0;
}

```