#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
using namespace std;
struct T {
  pair<int, int> f;
  pair<int, int> g;
};
inline pair<int, int> operator+(const pair<int, int> &a,
                                const pair<int, int> &b) {
  pair<int, int> res(a.first + b.first, a.second + b.second);
  if (res.first >= 998244353) res.first -= 998244353;
  if (res.second >= 998244353) res.second -= 998244353;
  return res;
}
inline pair<int, int> operator^(const pair<int, int> &a,
                                const pair<int, int> &b) {
  return pair<int, int>(
      ((long long)a.first * b.second + (long long)b.first * a.second) %
          998244353,
      (long long)a.second * b.second % 998244353);
}
inline pair<int, int> operator&(const pair<int, int> &a,
                                const pair<int, int> &b) {
  return pair<int, int>(
      ((long long)a.first * b.second + (long long)b.first * a.second +
       (long long)a.second * b.second) %
          998244353,
      (long long)a.second * b.second % 998244353);
}
inline T operator+(const T &a, const T &b) {
  T res;
  res.f = a.f + b.f;
  res.g = a.g + b.g;
  return res;
}
int a, b, c, d, n, m, k;
vector<int> sm[500002];
T rec(int v, int pr) {
  if ((int)((sm[v]).size()) == 1 && pr != -1) {
    pair<int, int> f = make_pair(0, 0);
    pair<int, int> g = f;
    f.second = 1;
    return T{f, g};
  }
  T cur;
  cur.f = make_pair(0, 1);
  cur.g = make_pair(0, 0);
  for (int _n(((int)((sm[v]).size())) - 1), i(0); i <= _n; i++) {
    int w = sm[v][i];
    if (w == pr) continue;
    auto c = rec(w, v);
    T nx;
    nx.f = nx.g = make_pair(0, 0);
    nx.f = (cur.f ^ c.g) + (cur.f ^ c.g) + (cur.f ^ c.f);
    nx.g = (cur.g ^ c.g) + (cur.g ^ c.g) + (cur.g ^ c.f) + (cur.g ^ c.f) +
           (cur.f & c.f);
    cur = nx;
  }
  return cur;
}
int main() {
  scanf("%d", &n);
  for (int _n((n - 1) - 1), i(0); i <= _n; i++) {
    scanf("%d%d", &a, &b);
    --a;
    --b;
    sm[a].push_back(b);
    sm[b].push_back(a);
  }
  if (n == 1) {
    printf("0\n");
    exit(0);
  }
  auto ans = rec(0, -1);
  int res = (ans.f.first + ans.g.first) % 998244353;
  res = (res * 2) % 998244353;
  printf("%d\n", res);
}

### Prompt

Please provide a cpp coded solution to the problem described below:

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>
#pragma GCC optimize("O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
using namespace std;
struct T {
  pair<int, int> f;
  pair<int, int> g;
};
inline pair<int, int> operator+(const pair<int, int> &a,
                                const pair<int, int> &b) {
  pair<int, int> res(a.first + b.first, a.second + b.second);
  if (res.first >= 998244353) res.first -= 998244353;
  if (res.second >= 998244353) res.second -= 998244353;
  return res;
}
inline pair<int, int> operator^(const pair<int, int> &a,
                                const pair<int, int> &b) {
  return pair<int, int>(
      ((long long)a.first * b.second + (long long)b.first * a.second) %
          998244353,
      (long long)a.second * b.second % 998244353);
}
inline pair<int, int> operator&(const pair<int, int> &a,
                                const pair<int, int> &b) {
  return pair<int, int>(
      ((long long)a.first * b.second + (long long)b.first * a.second +
       (long long)a.second * b.second) %
          998244353,
      (long long)a.second * b.second % 998244353);
}
inline T operator+(const T &a, const T &b) {
  T res;
  res.f = a.f + b.f;
  res.g = a.g + b.g;
  return res;
}
int a, b, c, d, n, m, k;
vector<int> sm[500002];
T rec(int v, int pr) {
  if ((int)((sm[v]).size()) == 1 && pr != -1) {
    pair<int, int> f = make_pair(0, 0);
    pair<int, int> g = f;
    f.second = 1;
    return T{f, g};
  }
  T cur;
  cur.f = make_pair(0, 1);
  cur.g = make_pair(0, 0);
  for (int _n(((int)((sm[v]).size())) - 1), i(0); i <= _n; i++) {
    int w = sm[v][i];
    if (w == pr) continue;
    auto c = rec(w, v);
    T nx;
    nx.f = nx.g = make_pair(0, 0);
    nx.f = (cur.f ^ c.g) + (cur.f ^ c.g) + (cur.f ^ c.f);
    nx.g = (cur.g ^ c.g) + (cur.g ^ c.g) + (cur.g ^ c.f) + (cur.g ^ c.f) +
           (cur.f & c.f);
    cur = nx;
  }
  return cur;
}
int main() {
  scanf("%d", &n);
  for (int _n((n - 1) - 1), i(0); i <= _n; i++) {
    scanf("%d%d", &a, &b);
    --a;
    --b;
    sm[a].push_back(b);
    sm[b].push_back(a);
  }
  if (n == 1) {
    printf("0\n");
    exit(0);
  }
  auto ans = rec(0, -1);
  int res = (ans.f.first + ans.g.first) % 998244353;
  res = (res * 2) % 998244353;
  printf("%d\n", res);
}

```