#include <bits/stdc++.h>
using namespace std;
class p445A {
 public:
  void solve() {
    long long n;
    cin >> n;
    unordered_map<long long, long long> cnt;
    long long mx = 0;
    for (int i = 0; i < n; i++) {
      long long a;
      cin >> a;
      mx = max(mx, a);
      cnt[a]++;
    }
    vector<long long> dp(mx + 1, 0);
    for (long long i = 1; i <= mx; i++) {
      dp[i] = max(dp[i], dp[i - 1]);
      if (!cnt.count(i)) continue;
      dp[i] = max(dp[i - 1], (i >= 2 ? dp[i - 2] : 0) + cnt[i] * i);
    }
    cout << dp[mx] << endl;
  }
};
class p550A {
 public:
  void solve() {
    string s;
    cin >> s;
    int l = -1;
    int cnt[2][2];
    memset(cnt, -1, sizeof(cnt));
    auto check = [&cnt](string &s, int flag) {
      for (int i = 0; i < s.size() - 1; i++) {
        if (s[i] == 'A' && s[i + 1] == 'B' && cnt[flag][0] == -1) {
          cnt[flag][0] = i + 1;
        }
        if (s[i] == 'B' && s[i + 1] == 'A' && cnt[flag][1] == -1) {
          cnt[flag][1] = i + 1;
        }
      }
    };
    check(s, 0);
    reverse(s.begin(), s.end());
    check(s, 1);
    if (cnt[0][1] != -1 && cnt[1][1] != -1 &&
        cnt[0][1] + 1 + cnt[1][1] + 1 <= s.size())
      cout << "YES" << endl;
    else if (cnt[0][0] != -1 && cnt[1][0] != -1 &&
             cnt[0][0] + 1 + cnt[1][0] + 1 <= s.size())
      cout << "YES" << endl;
    else
      cout << "NO" << endl;
  }
};
class p550C {
 public:
  void solve() {
    string s;
    cin >> s;
    int n = s.size();
    vector<vector<int>> dp(n + 1, vector<int>(8, 0));
    vector<vector<int>> pre(n + 1, vector<int>(8, -1));
    bool ok = false;
    for (int i = 1; i <= n; i++) {
      int ai = s[i - 1] - '0';
      dp[i][ai % 8] = 1;
      for (int j = 0; j < 8; j++) {
        if (dp[i - 1][j] == 1) {
          dp[i][(10 * j + ai) % 8] = 1;
          dp[i][j] = 1;
          pre[i][(10 * j + ai) % 8] = j;
          pre[i][j] = j;
        }
      }
      if (dp[i][0] == 1) ok = 1;
    }
    if (ok == 0)
      cout << "NO" << endl;
    else {
      cout << "YES" << endl;
      string ans;
      for (int i = 1; i <= n; i++) {
        if (dp[i][0] == 1) {
          int ci = i, cj = 0;
          while (ci > 0) {
            if (pre[ci][cj] == -1 || pre[ci][cj] != cj) {
              ans.append(1, s[ci - 1]);
            }
            if (pre[ci][cj] == -1) break;
            cj = pre[ci][cj];
            ci--;
          }
          reverse(ans.begin(), ans.end());
          cout << ans << endl;
          break;
        }
      }
    }
  }
};
class p545C {
 public:
  void solve() {
    int n;
    cin >> n;
    vector<pair<long long, long long>> tree;
    for (int i = 0; i < n; i++) {
      long long x, h;
      cin >> x >> h;
      tree.emplace_back(x, h);
    }
    if (n == 1)
      cout << 1 << endl;
    else {
      int res = 1;
      int pre = 0;
      for (int i = 1; i < n; i++) {
        if (pre == 0) {
          if (tree[i].first - tree[i].second > tree[i - 1].first) {
            res++;
          } else if (i == n - 1 ||
                     tree[i + 1].first > tree[i].first + tree[i].second) {
            pre = 1;
            res++;
          }
        } else {
          if (tree[i].first - tree[i].second >
              tree[i - 1].first + tree[i - 1].second) {
            pre = 0;
            res++;
          } else if (i == n - 1 ||
                     tree[i + 1].first > tree[i].first + tree[i].second) {
            pre = 1;
            res++;
          } else
            pre = 0;
        }
      }
      cout << res << endl;
    }
  }
};
class p166E {
 public:
  vector<vector<long long>> matrixmul(const vector<vector<long long>> &a,
                                      const vector<vector<long long>> &b) {
    int n = a.size();
    vector<vector<long long>> c(n, vector<long long>(n, 0));
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        for (int k = 0; k < n; k++) {
          c[i][j] += a[i][k] * b[k][j];
          c[i][j] %= 1000000007;
        }
      }
    }
    return c;
  }
  vector<vector<long long>> fmul(vector<vector<long long>> &matrix, int n) {
    vector<vector<long long>> res(matrix.size(),
                                  vector<long long>(matrix[0].size(), 0));
    for (int i = 0; i < matrix.size(); i++) res[i][i] = 1;
    while (n >= 1) {
      if (n & 1) {
        res = matrixmul(res, matrix);
      }
      n = n >> 1;
      matrix = matrixmul(matrix, matrix);
    }
    return res;
  }
  void solve() {
    int n;
    cin >> n;
    vector<vector<long long>> a(4, vector<long long>(4, 1));
    for (int i = 0; i < 4; i++) a[i][i] = 0;
    auto res = fmul(a, n);
    cout << res[3][3] << endl;
  }
};
class p676C {
 public:
  void solve() {
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    int a = 0, b = 0;
    int res = 0;
    for (int l = 0, r = 0; l < n; l++) {
      while (min(a, b) <= k && r < n) {
        res = max(res, a + b);
        if (s[r] == 'a')
          a++;
        else
          b++;
        r++;
      }
      if (min(a, b) <= k) res = max(res, a + b);
      if (s[l] == 'a')
        a--;
      else
        b--;
    }
    cout << res << endl;
  }
};
class p839C {
 public:
  double ans;
  vector<vector<int>> e;
  void dfs(int fa, int cur, double pre) {
    double pro = e[cur].size() <= 1
                     ? (fa == -1 ? pre : 0.0)
                     : pre / (fa == -1 ? e[cur].size() : (e[cur].size() - 1));
    for (int next : e[cur]) {
      if (next == fa) continue;
      ans += pro;
      dfs(cur, next, pro);
    }
  }
  void solve() {
    int n;
    cin >> n;
    e.clear();
    e = vector<vector<int>>(n);
    for (int i = 0; i < n - 1; i++) {
      int u, v;
      cin >> u >> v;
      u--;
      v--;
      e[u].push_back(v);
      e[v].push_back(u);
    }
    ans = 0.0;
    dfs(-1, 0, 1);
    printf("%.15lf\n", ans);
  }
};
class p1272D {
 public:
  void solve() {
    int n;
    cin >> n;
    vector<int> a(n, 0);
    for (int i = 0; i < n; i++) cin >> a[i];
    vector<int> l(n, 0), r(n, 0);
    l[0] = 1;
    for (int i = 1; i < n; i++) {
      l[i] = 1;
      if (a[i] > a[i - 1]) l[i] += l[i - 1];
    }
    r[n - 1] = 1;
    for (int i = n - 2; i >= 0; i--) {
      r[i] = 1;
      if (a[i] < a[i + 1]) r[i] += r[i + 1];
    }
    int res = 0;
    for (int i = 0; i < n; i++) {
      res = max(res, l[i]);
      if (i < n - 2 && a[i] < a[i + 2]) res = max(res, l[i] + r[i + 2]);
    }
    cout << res << endl;
  }
};
class p1253C {
 public:
  void solve() {
    long long m, n;
    cin >> n >> m;
    vector<long long> a(n, 0);
    for (int i = 0; i < n; i++) cin >> a[i];
    sort(a.begin(), a.end());
    vector<long long> res;
    vector<long long> sum(n + 1, 0);
    for (int i = 1; i <= n; i++) {
      sum[i] = sum[i - 1] + a[i - 1];
    }
    vector<long long> x(n + 1, 0);
    for (int i = 1; i <= n; i++) {
      x[i] = sum[i] + x[max(0ll, i - m)];
      res.push_back(x[i]);
    }
    for (auto i : res) cout << i << " ";
    cout << endl;
  }
};
class p1234C {
 public:
  void solve() {
    int q;
    cin >> q;
    for (int i = 0; i < q; i++) {
      vector<string> s(2);
      int n;
      cin >> n >> s[0] >> s[1];
      int row = 0, pos = 0;
      bool ok = true;
      for (pos = 0; pos < n; pos++) {
        if (s[row][pos] >= '3') {
          if (s[1 - row][pos] < '3') {
            ok = false;
            break;
          } else {
            row = 1 - row;
          }
        }
      }
      if (ok && row == 1 && pos == n)
        cout << "YES" << endl;
      else
        cout << "NO" << endl;
    }
  }
};
class p1307C {
 public:
  void solve() {
    string s;
    cin >> s;
    vector<long long> cnt(26, 0);
    vector<long long> dict(1000, 0);
    long long mx = 0;
    for (int i = 0; i < s.size(); i++) {
      for (int j = 0; j < 26; j++) {
        dict[j * 30 + s[i] - 'a'] += cnt[j];
        mx = max(mx, dict[j * 30 + s[i] - 'a']);
      }
      cnt[s[i] - 'a']++;
      mx = max(mx, cnt[s[i] - 'a']);
    }
    cout << mx << endl;
  }
};
class p1207C {
 public:
  void solve() {
    int t;
    cin >> t;
    while (t--) {
      long long n, a, b;
      cin >> n >> a >> b;
      string s;
      cin >> s;
      vector<vector<long long>> dp(n + 1, vector<long long>(2, -1));
      dp[0][0] = b;
      for (int i = 1; i <= n; i++) {
        if (s[i - 1] == '1') {
          if (dp[i - 1][1] != -1) dp[i][1] = dp[i - 1][1] + 2 * b + a;
          if (dp[i - 1][0] != -1)
            dp[i][1] = dp[i][1] != -1
                           ? min(dp[i][1], dp[i - 1][0] + 3 * (a + b) - a)
                           : dp[i - 1][0] + 3 * (a + b) - a;
        } else {
          if (dp[i - 1][1] != -1) dp[i][1] = dp[i - 1][1] + 2 * b + a;
          if (dp[i - 1][0] != -1)
            dp[i][1] = dp[i][1] != -1
                           ? min(dp[i][1], dp[i - 1][0] + 3 * (a + b) - a)
                           : dp[i - 1][0] + 3 * (a + b) - a;
          if (dp[i - 1][0] != -1) dp[i][0] = dp[i - 1][0] + a + b;
          if (dp[i - 1][1] != -1)
            dp[i][0] = dp[i][0] != -1 ? min(dp[i][0], dp[i - 1][1] + 2 * a + b)
                                      : dp[i - 1][1] + 2 * a + b;
        }
      }
      cout << dp[n][0] << endl;
    }
  }
};
class p1105C {
 public:
  void solve() {
    long long n, l, r;
    cin >> n >> l >> r;
    l--;
    long long zero = r / 3 - l / 3;
    long long one = (r + 2) / 3 - (l + 2) / 3;
    long long two = (r + 1) / 3 - (l + 1) / 3;
    vector<vector<long long>> dp(n, vector<long long>(3, 0));
    dp[0][0] = zero;
    dp[0][1] = one;
    dp[0][2] = two;
    for (int i = 1; i < n; i++) {
      dp[i][0] =
          (dp[i - 1][0] * zero + dp[i - 1][1] * two + dp[i - 1][2] * one) %
          1000000007;
      dp[i][1] =
          (dp[i - 1][0] * one + dp[i - 1][1] * zero + dp[i - 1][2] * two) %
          1000000007;
      dp[i][2] =
          (dp[i - 1][0] * two + dp[i - 1][1] * one + dp[i - 1][2] * zero) %
          1000000007;
    }
    cout << dp[n - 1][0] << endl;
  }
};
class p611C {
 public:
  void solve() {
    int h, w;
    cin >> h >> w;
    vector<string> g(h);
    for (int i = 0; i < h; i++) cin >> g[i];
    vector<vector<vector<int>>> dp(
        h + 1, vector<vector<int>>(w + 1, vector<int>(2, 0)));
    for (int i = 1; i <= h; i++) {
      for (int j = 1; j <= w; j++) {
        for (int k = 0; k < 2; k++)
          dp[i][j][k] = dp[i - 1][j][k] + dp[i][j - 1][k] - dp[i - 1][j - 1][k];
        if (g[i - 1][j - 1] == '#') {
          continue;
        }
        if (i >= 2 && g[i - 2][j - 1] == '.') dp[i][j][0]++;
        if (j >= 2 && g[i - 1][j - 2] == '.') dp[i][j][1]++;
      }
    }
    int q;
    cin >> q;
    for (int i = 1; i <= q; i++) {
      int r1, c1, r2, c2;
      cin >> r1 >> c1 >> r2 >> c2;
      int res = 0;
      res +=
          dp[r2][c2][0] - dp[r1][c2][0] - dp[r2][c1 - 1][0] + dp[r1][c1 - 1][0];
      res +=
          dp[r2][c2][1] - dp[r2][c1][1] - dp[r1 - 1][c2][1] + dp[r1 - 1][c1][1];
      cout << res << endl;
    }
  }
};
class p1051C {
 public:
  void solve() {
    int t, n = 0;
    cin >> t;
    vector<int> a(t, 0);
    for (auto &i : a) {
      cin >> i;
      n = max(n, i);
    }
    vector<int> cnt(n + 1, 0);
    vector<int> used(n + 1, -1);
    for (int i = 0; i < t; i++) {
      cnt[a[i]]++;
    }
    int odd = 0, even = 0;
    for (int i = 0; i <= n; i++) {
      if (cnt[i] == 1)
        odd++;
      else if (cnt[i] > 2)
        even++;
    }
    if (odd % 2 == 1 && even == 0) {
      cout << "NO" << endl;
      return;
    }
    if (odd % 2 == 1) {
      for (int i = 0; i <= n; i++)
        if (cnt[i] > 2) {
          cnt[i] = 1;
          break;
        }
    }
    cout << "YES" << endl;
    string s;
    char ch[2] = {'A', 'B'};
    int flag = 0;
    for (int i = 0; i < t; i++) {
      if (cnt[a[i]] != 1)
        s.append(1, 'A');
      else {
        if (used[a[i]] != -1)
          s.append(1, ch[used[a[i]] ^ 1]);
        else {
          used[a[i]] = flag;
          s.append(1, ch[flag]);
          flag ^= 1;
        }
      }
    }
    cout << s << endl;
  }
};
class p1313C1 {
 public:
  void solve() {
    int n;
    cin >> n;
    vector<long long> a(n, 0);
    for (auto &i : a) cin >> i;
    vector<vector<long long>> f(2, vector<long long>(n, 0));
    stack<int> left, right;
    auto monostack = [&n, &f](vector<long long> &a, stack<int> &left,
                              int flag) {
      for (int i = 0; i < n; i++) {
        while (left.size() != 0 && a[left.top()] > a[i]) left.pop();
        long long pre = left.size() == 0 ? 0 : f[flag][left.top()];
        long long len = left.size() == 0 ? i + 1 : i - left.top();
        f[flag][i] = pre + len * a[i];
        left.push(i);
      }
    };
    monostack(a, left, 0);
    reverse(a.begin(), a.end());
    monostack(a, right, 1);
    reverse(f[1].begin(), f[1].end());
    reverse(a.begin(), a.end());
    long long id = -1, mx = 0;
    for (int i = 0; i < n; i++) {
      if (f[0][i] + f[1][i] - a[i] > mx) {
        id = i;
        mx = f[0][i] + f[1][i] - a[i];
      }
    }
    vector<long long> res(n, 0);
    res[id] = a[id];
    for (long long i = id - 1; i >= 0; i--) {
      if (a[i] > res[i + 1])
        res[i] = res[i + 1];
      else
        res[i] = a[i];
    }
    for (long long i = id + 1; i < n; i++) {
      if (a[i] > res[i - 1])
        res[i] = res[i - 1];
      else
        res[i] = a[i];
    }
    for (long long i : res) cout << i << " ";
    cout << endl;
  }
};
class p982C {
 public:
  int ans = 0;
  vector<vector<int>> edge;
  int dfs(int cur, int fa) {
    int odd = 0;
    for (auto child : edge[cur]) {
      if (child == fa) continue;
      int temp = dfs(child, cur);
      if (temp == 0)
        ans++;
      else
        odd++;
    }
    if (odd % 2 == 1)
      return 0;
    else
      return 1;
  }
  void solve() {
    int n;
    cin >> n;
    ans = 0;
    edge = vector<vector<int>>(n);
    for (int i = 0; i < n - 1; i++) {
      int u, v;
      cin >> u >> v;
      u--;
      v--;
      edge[u].push_back(v);
      edge[v].push_back(u);
    }
    if (dfs(0, -1) != 0) {
      cout << -1 << endl;
    } else
      cout << ans << endl;
  }
};
class p891C {
 public:
  int gcd(int x, int y) {
    if (y == 0) return x;
    return gcd(y, x % y);
  }
  void solve() {
    int n;
    cin >> n;
    vector<int> a(n, 0);
    int cnt = 0;
    for (int i = 0; i < n; i++) {
      cin >> a[i];
      if (a[i] == 1) cnt++;
    }
    if (cnt > 0) {
      cout << n - cnt << endl;
      return;
    }
    bool ok = false;
    int len = n + 1;
    for (int l = 0; l < n; l++) {
      int temp = a[l];
      for (int r = l; r < n; r++) {
        temp = gcd(temp, a[r]);
        if (temp == 1) {
          len = min(len, r - l);
          break;
        }
      }
    }
    if (len == n + 1)
      cout << -1 << endl;
    else
      cout << len + n - 1 << endl;
  }
};
class p877B {
 public:
  void solve() {
    string s;
    cin >> s;
    int n = s.size();
    vector<vector<int>> a(2, vector<int>(n + 1, 0));
    for (int i = 0; i < s.size(); i++) {
      int cur = s[i] - 'a';
      a[0][i + 1] += a[0][i];
      a[1][i + 1] += a[1][i];
      a[cur][i + 1]++;
    }
    int res = 0;
    for (int i = 0; i <= n; i++) {
      for (int j = i; j <= n; j++) {
        int t1 = a[1][i];
        int t2 = a[0][j] - a[0][i];
        int t3 = a[1][n] - a[1][j];
        res = max(res, n - t1 - t2 - t3);
      }
    }
    cout << res << endl;
  }
};
class p1005D {
 public:
  void solve() {
    string s;
    cin >> s;
    int n = s.size();
    vector<int> dp(n + 1, 0);
    int sum = 0;
    unordered_map<int, int> cnt;
    cnt[0] = 0;
    int res = 0;
    for (int i = 1; i <= n; i++) {
      sum += (s[i - 1] - '0');
      sum %= 3;
      dp[i] = dp[i - 1];
      if (cnt.count((sum))) {
        dp[i] = max(dp[i], dp[cnt[sum]] + 1);
      }
      res = max(res, dp[i]);
      cnt[sum] = i;
    }
    cout << res << endl;
  }
};
class p264B {
 public:
  int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
  }
  void solve() {
    int n;
    cin >> n;
    vector<int> a(n, 0);
    for (auto &i : a) cin >> i;
    int res = 0;
    unordered_map<int, int> dp;
    for (int &i : a) {
      if (i == 1) {
        res = max(res, 1);
        continue;
      }
      vector<int> temp;
      int cur = 0;
      for (int j = 2; j <= i / j; j++) {
        if (i % j == 0) {
          temp.push_back(j);
          cur = max(cur, dp[j] + 1);
          while (i % j == 0) i /= j;
        }
      }
      if (i > 1) {
        temp.push_back(i);
        cur = max(cur, dp[i] + 1);
      }
      for (int j : temp) dp[j] = max(dp[j], cur);
      res = max(cur, res);
    }
    cout << res << endl;
  }
};
class p553A {
 public:
  void solve() {
    int k;
    cin >> k;
    vector<long long> a(k, 0);
    vector<long long> dp(k, 0);
    int maxn = 1010;
    vector<vector<long long>> f(maxn, vector<long long>(maxn, 0));
    f[0][0] = 1;
    for (int i = 1; i < maxn; i++) {
      f[i][0] = 1;
      for (int j = 1; j <= i; j++) {
        f[i][j] = (f[i - 1][j] + f[i - 1][j - 1]) % 1000000007;
      }
    }
    for (auto &i : a) cin >> i;
    long long sum = a[0];
    dp[0] = 1;
    for (long long i = 1; i < k; i++) {
      sum += a[i] - 1;
      dp[i] = (dp[i - 1] * f[sum][a[i] - 1]) % 1000000007;
      sum++;
    }
    cout << dp.back() % 1000000007 << endl;
  }
};
class p322B {
 public:
  void solve() {
    int n, k;
    cin >> n >> k;
    vector<long long> v(n, 0);
    vector<long long> sum(n + 1, 0);
    vector<long long> dp(n + 1, 0);
    vector<long long> index(n + 1, 0);
    dp[0] = 0;
    index[0] = 0;
    long long res = 0;
    for (int i = 1; i <= n; i++) {
      cin >> v[i - 1];
      sum[i] += sum[i - 1] + v[i - 1];
      dp[i] = dp[i - 1];
      index[i] = index[i - 1];
      if (i >= k) {
        if (sum[i] - sum[i - k] > dp[i]) {
          dp[i] = sum[i] - sum[i - k];
          index[i] = i - k + 1;
        }
        res = max(res, sum[i] - sum[i - k] + dp[i - k]);
      }
    }
    vector<pair<long long, long long>> ans;
    for (int i = 1; i <= n; i++) {
      if (i >= k) {
        if (res == dp[i - k] + sum[i] - sum[i - k]) {
          ans.emplace_back(index[i - k], i - k + 1);
        }
      }
    }
    sort(ans.begin(), ans.end());
    cout << ans.begin()->first << " " << ans.begin()->second << endl;
  }
};
class p1084C {
 public:
  void solve() {
    string s;
    cin >> s;
    int n = s.size();
    vector<long long> a;
    long long sum = 0;
    for (int i = 1; i <= n; i++) {
      if (s[i - 1] == 'a') {
        sum++;
      } else if (s[i - 1] == 'b') {
        a.push_back(sum);
        sum = 0;
      }
    }
    if (sum != 0) a.push_back(sum);
    long long res = 1;
    if (a.size() == 0) {
      cout << 0 << endl;
      return;
    }
    for (auto i : a) {
      res = (res * (i + 1)) % 1000000007;
    }
    res = (res - 1 + 1000000007) % 1000000007;
    cout << res << endl;
  }
};
class p991D {
 public:
  void solve() {
    vector<string> a(2);
    cin >> a[0] >> a[1];
    int n = a[0].size();
    if (n == 1) {
      cout << 0 << endl;
      return;
    }
    vector<vector<int>> dp(n + 1, vector<int>(3, 0));
    vector<int> v(n, 0);
    for (int i = 0; i < n; i++) {
      if (a[0][i] == '0') v[i]++;
      if (a[1][i] == '0') v[i]++;
    }
    for (int i = 2; i <= n; i++) {
      dp[i][2] = max(dp[i - 1][0], max(dp[i - 1][1], dp[i - 1][2]));
      if (v[i - 1] == 0) continue;
      int pre = max(dp[i - 2][0], max(dp[i - 2][1], dp[i - 2][2]));
      if (v[i - 1] == 2) {
        if (v[i - 2] > 0) {
          if (v[i - 2] == 2) {
            dp[i][0] = max(dp[i][0], pre + 1);
            dp[i][1] = max(dp[i][1], pre + 1);
            dp[i][1] = max(dp[i][1], max(dp[i - 1][0], dp[i - 1][2]) + 1);
          } else
            dp[i][1] = max(dp[i][1], dp[i - 1][2] + 1);
        }
      } else {
        if (v[i - 2] == 2) {
          dp[i][0] = max(dp[i][0], pre + 1);
        }
      }
    }
    cout << max(dp[n][0], max(dp[n][1], dp[n][2])) << endl;
  }
};
class p855B {
 public:
  void solve() {
    long long n;
    cin >> n;
    vector<long long> v(3, 0);
    cin >> v[0] >> v[1] >> v[2];
    vector<long long> a(n, 0);
    for (auto &i : a) cin >> i;
    vector<vector<long long>> dp(n, vector<long long>(3, 0));
    dp[0][0] = v[0] * a[0];
    dp[0][1] = v[0] * a[0] + v[1] * a[0];
    dp[0][2] = v[0] * a[0] + v[1] * a[0] + v[2] * a[0];
    for (int i = 1; i < n; i++) {
      for (int j = 0; j < 3; j++) {
        dp[i][j] = dp[i - 1][j];
        long long temp = 0;
        for (int k = j; k >= 0; k--) {
          temp += v[k] * a[i];
          dp[i][j] = max(dp[i][j], temp + (k - 1 >= 0 ? dp[i - 1][k - 1] : 0));
        }
      }
    }
    cout << dp[n - 1][2] << endl;
  }
};
class p873B {
 public:
  void solve() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    unordered_map<int, int> cnt;
    int zero = 0, one = 0;
    int res = 0;
    cnt[0] = -1;
    for (int i = 0; i < n; i++) {
      if (s[i] == '0')
        zero++;
      else
        one++;
      int diff = zero - one;
      if (cnt.count(diff)) {
        res = max(res, i - cnt[diff]);
      } else
        cnt[diff] = i;
    }
    cout << res << endl;
  }
};
class p340D {
 public:
  void solve() {
    int n;
    cin >> n;
    vector<int> a(n, 0);
    for (auto &i : a) cin >> i;
    vector<int> dp;
    for (int i : a) {
      auto pos = upper_bound(dp.begin(), dp.end(), i) - dp.begin();
      if (pos == dp.size())
        dp.push_back(i);
      else
        dp[pos] = i;
    }
    cout << dp.size() << endl;
  }
};
class p1081C {
 public:
  void solve() {
    long long n, m, k;
    cin >> n >> m >> k;
    vector<vector<long long>> dp(n, vector<long long>(k + 1, 0));
    long long modulo = 998244353;
    dp[0][0] = m;
    for (int i = 1; i < n; i++) {
      for (int j = k; j >= 0; j--) {
        dp[i][j] =
            (dp[i - 1][j] + (j > 0 ? dp[i - 1][j - 1] : 0) * (m - 1)) % modulo;
      }
    }
    cout << dp[n - 1][k] << endl;
  }
};
class p761C {
 public:
  void solve() {
    int n, m;
    cin >> n >> m;
    vector<string> v(n);
    for (int i = 0; i < n; i++) cin >> v[i];
    vector<vector<int>> a(n, vector<int>(3, -1));
    auto check = [](char c) {
      if (c == '#' || c == '*' || c == '&') return true;
      return false;
    };
    for (int i = 0; i < n; i++) {
      for (int j = m - 1; j >= 0; j--) {
        if (isdigit(v[i][j]))
          a[i][0] = a[i][0] == -1 ? min(j, m - j) : min(a[i][0], min(j, m - j));
        if (isalpha(v[i][j]))
          a[i][1] = a[i][1] == -1 ? min(j, m - j) : min(a[i][1], min(j, m - j));
        if (check(v[i][j]))
          a[i][2] = a[i][2] == -1 ? min(j, m - j) : min(a[i][2], min(j, m - j));
      }
    }
    vector<vector<int>> dp(n + 1, vector<int>(1 << 3, 10000));
    dp[0][0] = 0;
    for (int i = 1; i <= n; i++) {
      dp[i][0] = dp[i - 1][0];
      for (int j = 1; j < (1 << 3); j++) {
        dp[i][j] = dp[i - 1][j];
        for (int k = 0; k < 3; k++) {
          if (((1 << k) & j) != 0 && a[i - 1][k] != -1) {
            int pre = (1 << k) ^ j;
            dp[i][j] = min(dp[i][j], dp[i - 1][pre] + a[i - 1][k]);
          }
        }
      }
    }
    cout << dp[n][(1 << 3) - 1] << endl;
  }
};
class p858C {
 public:
  void solve() {
    string s;
    cin >> s;
    unordered_set<char> dict{'a', 'e', 'i', 'o', 'u'};
    int block = 0, kind = 0;
    vector<char> res;
    bool first = 1;
    for (int i = 0; i < s.size(); i++) {
      if (!dict.count(s[i])) {
        block++;
        if (block > 2 && (s[i] != s[i - 1] || s[i - 1] != s[i - 2])) {
          res.push_back(' ');
          block = 1;
        }
      } else {
        block = kind = 0;
      }
      res.push_back(s[i]);
    }
    for (auto i : res) cout << i;
    cout << endl;
  }
};
class p204A {
 public:
  long long getTen(int x) {
    if (x == 0) return 1;
    long long temp = getTen(x / 2);
    if (x % 2 == 1) return temp * temp * 10;
    return temp * temp;
  }
  long long getDig(long long x) {
    if (x <= 0) return 0;
    if (x <= 9) return x;
    long long res = 0;
    vector<long long> a;
    while (x > 0) {
      a.emplace_back(x % 10);
      x /= 10;
    }
    reverse(a.begin(), a.end());
    int n = a.size();
    for (int i = 0; i < n; i++) {
      long long temp = getTen(max(0, n - 2 - (i + 1) + 1));
      int up = i > 0 ? 10 : a[i];
      for (int j = 1; j < up; j++) {
        res += temp;
      }
    }
    long long temp = 0;
    for (int i = 1; i < n - 1; i++) temp = temp * 10 + a[i];
    if (a.front() <= a.back()) temp++;
    res += temp;
    return res;
  }
  void solve() {
    long long l, r;
    cin >> l >> r;
    cout << getDig(r) - getDig(l - 1) << endl;
  }
};
class p859C {
 public:
  void solve() {
    int n;
    cin >> n;
    vector<int> a(n, 0);
    for (auto &i : a) cin >> i;
    vector<int> dp(n, 0);
    vector<int> sum(n, 0);
    sum[n - 1] = a[n - 1];
    dp[n - 1] = a[n - 1];
    for (int i = n - 2; i >= 0; i--) sum[i] = sum[i + 1] + a[i];
    for (int i = n - 2; i >= 0; i--) {
      dp[i] = max(dp[i + 1], sum[i + 1] - dp[i + 1] + a[i]);
    }
    cout << sum[0] - dp[0] << " " << dp[0] << endl;
  }
};
class p159D {
 public:
  void solve() {
    string s;
    cin >> s;
    long long n = s.size();
    vector<vector<long long>> done(n, vector<long long>(n, 0));
    vector<long long> dp(n, 0);
    vector<long long> sum(n, 0);
    auto check = [&s, &done, &n](int l, int r) {
      while (l >= 0 && r < n && s[l] == s[r]) {
        done[l][r] = 1;
        l--;
        r++;
      }
    };
    for (int i = 0; i < n; i++) {
      int l = i, r = i;
      check(l, r);
      l = i, r = i + 1;
      check(l, r);
    }
    dp[0] = 0;
    sum[0] = 1;
    for (int i = 1; i < n; i++) {
      long long cnt = 0, cur = 0;
      for (int j = 0; j <= i; j++) {
        if (done[j][i]) {
          cnt++;
          cur += j == 0 ? 0 : sum[j - 1];
        }
      }
      dp[i] = dp[i - 1] + cur;
      sum[i] = sum[i - 1] + cnt;
    }
    cout << dp[n - 1] << endl;
  }
};
class p255C {
 public:
  void solve() {
    int n;
    cin >> n;
    vector<int> a(n, 0);
    unordered_map<int, vector<int>> cnt;
    for (int i = 0; i < n; i++) {
      cin >> a[i];
      cnt[a[i]].push_back(i);
    }
    vector<int> v;
    int res = 0;
    for (auto it : cnt) {
      v.push_back(it.first);
      res = max(res, (int)it.second.size());
    }
    int sz = v.size();
    auto check = [&cnt, &v](int a, int b) {
      int res = 0;
      int i = 0, j = 0, lena = cnt[v[a]].size(), lenb = cnt[v[b]].size();
      while (i < lena && j < lenb) {
        if (cnt[v[a]][i] < cnt[v[b]][j]) {
          while (i < lena && cnt[v[a]][i] < cnt[v[b]][j]) i++;
          if (i < lena) res++;
        } else {
          while (j < lenb && cnt[v[b]][j] < cnt[v[a]][i]) j++;
          if (j < lenb) res++;
        }
      }
      return res + 2;
    };
    for (int i = 0; i < sz; i++) {
      for (int j = i + 1; j < sz; j++) {
        res = max(res, check(i, j));
      }
    }
    cout << res << endl;
  }
  void solve2() {
    int n;
    cin >> n;
    vector<int> a(n, 0);
    for (int i = 0; i < n; i++) cin >> a[i];
    vector<vector<int>> dp(n, vector<int>(n, 0));
    int res = 1;
    for (int i = 1; i < n; i++) {
      int k = -1;
      for (int j = 0; j < i; j++) {
        if (k == -1)
          dp[i][j] = 2;
        else
          dp[i][j] = dp[j][k] + 1;
        if (a[i] == a[j]) k = j;
        res = max(res, dp[i][j]);
      }
    }
    cout << res << endl;
  }
};
class p868C {
 public:
  void solve() {
    int n, k;
    cin >> n >> k;
    unordered_map<int, int> cnt;
    for (int i = 0; i < n; i++) {
      int mask = 0;
      for (int j = 0; j < k; j++) {
        int t = 0;
        cin >> t;
        if (t == 1) mask |= (1 << j);
      }
      cnt[mask]++;
    }
    bool flag = false;
    for (int i = 0; i < (1 << k); i++) {
      for (int j = 0; j < (1 << k); j++) {
        if ((i & j) == 0 && (cnt[i] && cnt[j])) flag = true;
      }
    }
    if (flag)
      cout << "YES" << endl;
    else
      cout << "NO" << endl;
  }
};
class p22B {
 public:
  void solve() {
    int n, m;
    cin >> n >> m;
    vector<string> a(n);
    vector<vector<int>> up(n, vector<int>(m, 0));
    vector<vector<int>> left(n, vector<int>(m, 0));
    for (int i = 0; i < n; i++) {
      cin >> a[i];
      for (int j = 0; j < m; j++) {
        if (a[i][j] == '0') {
          up[i][j] = left[i][j] = 1;
          if (i - 1 >= 0) up[i][j] += up[i - 1][j];
          if (j > 0) left[i][j] += left[i][j - 1];
        }
      }
    }
    int res = 0;
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        if (a[i][j] == '1') continue;
        int len = 1000000;
        for (int k = 1; k <= up[i][j]; k++) {
          len = min(len, left[i - k + 1][j]);
          res = max(res, (len + k) * 2);
        }
      }
    }
    cout << res << endl;
  }
};
class p566F {
 public:
  void solve() {
    int n;
    cin >> n;
    vector<int> a(n, 0);
    unordered_map<int, int> cnt;
    int mx = -1;
    for (int i = 0; i < n; i++) {
      cin >> a[i];
      mx = max(mx, a[i]);
    }
    vector<int> dp(mx + 1, 1);
    for (int i = 0; i < n; i++) {
      for (int j = 2 * a[i]; j <= mx; j += a[i]) {
        dp[j] = max(dp[j], dp[a[i]] + 1);
      }
    }
    int res = 0;
    for (int i = 0; i < n; i++) res = max(res, dp[a[i]]);
    cout << res << endl;
  }
};
class p191A {
 public:
  void solve() {
    int n;
    cin >> n;
    vector<string> s(n);
    vector<vector<int>> dp(26, vector<int>(26, -1));
    for (int i = 0; i < n; i++) cin >> s[i];
    int res = 0;
    for (int i = 0; i < n; i++) {
      int st = s[i].front() - 'a', ed = s[i].back() - 'a';
      for (int j = 0; j < 26; j++) {
        if (dp[j][st] != -1) {
          dp[j][ed] = max(dp[j][ed], dp[j][st] + (int)s[i].size());
        }
      }
      dp[st][ed] = max(dp[st][ed], (int)s[i].size());
    }
    for (int i = 0; i < 26; i++) res = max(res, dp[i][i]);
    cout << res << endl;
  }
};
class p417A {
 public:
  void solve() {
    int c, d, n, m, k;
    cin >> c >> d >> n >> m >> k;
    int res = 100000000;
    int remain = max(0, n * m - k);
    if (remain == 0) {
      cout << 0 << endl;
      return;
    }
    for (int i = 0; i * n <= remain + n - 1; i++) {
      int left = max(0, remain - i * n);
      res = min(res, i * c + left * d);
    }
    cout << res << endl;
  }
};
class p10B {
 public:
  void solve() {
    int n, k, m;
    cin >> n >> k;
    vector<vector<vector<int>>> dp(
        k + 1, vector<vector<int>>(k + 1, vector<int>(k + 1, 0x3f3f3f3f)));
    for (int i = 1; i <= k; i++) {
      for (int j = 1; j <= k; j++) {
        dp[i][j][0] = 0;
        for (int r = 1; r + j - 1 <= k; r++) {
          dp[i][j][r] = dp[i][j][r - 1] + abs(i - (k + 1) / 2) +
                        abs(j + r - 1 - (k + 1) / 2);
        }
      }
    }
    while (n--) {
      cin >> m;
      int ans = 0x3f3f3f3f, x, l, r;
      for (int i = 1; i <= k; i++) {
        for (int j = 1; j <= k; j++) {
          if (dp[i][j][m] < ans) {
            x = i;
            l = j;
            r = j + m - 1;
            ans = dp[i][j][m];
          }
        }
      }
      if (ans == 0x3f3f3f3f)
        cout << -1 << endl;
      else {
        cout << x << " " << l << " " << r << endl;
        for (int i = 1; i <= k; i++) {
          for (int j = 1; j + i - 1 <= k; j++) {
            if (!(i + j - 1 < l || i > r)) {
              dp[x][i][j] = 0x3f3f3f3f;
            }
          }
        }
      }
    }
  }
};
class p74B {
 public:
  void solve() {
    int n, m, k;
    cin >> n >> m >> k;
    string to, dir;
    cin >> to >> dir;
    int d = 0;
    string t;
    cin >> t;
    if (dir == "head")
      d = -1;
    else
      d = 1;
    int res = 0;
    bool win = true;
    auto move = [&k, &d, &n]() {
      k += d;
      if (k == 0)
        k = 2, d = -d;
      else if (k == n + 1)
        k = n - 1, d = -d;
    };
    for (int i = 0; i < t.size(); i++) {
      if (t[i] == '0') {
        if ((m - k) * d >= 0)
          m += d;
        else
          m -= d;
        if (m == 0) m = 1;
        if (m == n + 1) m = n;
        if (m == k) {
          win = false, res = i;
          break;
        }
        move();
      } else {
        move();
        if (d == -1) {
          m = (k == n ? 1 : n);
        } else
          m = (k == 1 ? n : 1);
      }
      if (m == k) {
        win = false, res = i;
        break;
      }
    }
    if (win)
      cout << "Stowaway" << endl;
    else {
      cout << "Controller " << res + 1 << endl;
    }
  }
};
class p212E {
 public:
  int n;
  int res[50005];
  vector<vector<int>> e;
  int dfs(int cur, int fa) {
    int cnt = 1;
    vector<int> sub;
    for (auto c : e[cur]) {
      if (c == fa) continue;
      auto temp = dfs(c, cur);
      sub.push_back(temp);
      cnt += temp;
    }
    if (cnt == 1) return cnt;
    if (n - cnt != 0) sub.push_back(n - cnt);
    vector<vector<bool>> dp =
        vector<vector<bool>>(sub.size() + 1, vector<bool>(n + 1, 0));
    dp[0][0] = 1;
    for (int j = 1; j <= sub.size(); j++) {
      for (int i = 1; i < n - 1; i++) {
        dp[j][i] = dp[j - 1][i];
        if (i >= sub[j - 1] && dp[j - 1][i - sub[j - 1]]) dp[j][i] = 1;
        if (dp[j][i]) {
          res[i] = res[n - 1 - i] = 1;
        }
      }
    }
    return cnt;
  }
  void solve() {
    cin >> n;
    memset(res, 0, sizeof(res));
    e = vector<vector<int>>(n + 1);
    for (int i = 0; i < n - 1; i++) {
      int x, y;
      cin >> x >> y;
      e[x].push_back(y);
      e[y].push_back(x);
    }
    dfs(1, 0);
    vector<pair<long long, long long>> cnt;
    for (int i = 1; i < n - 1; i++) {
      if (res[i] == 1) cnt.emplace_back(i, n - 1 - i);
    }
    cout << cnt.size() << endl;
    for (auto i : cnt) cout << i.first << " " << i.second << endl;
  }
};
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  p212E ans;
  ans.solve();
  return 0;
}

### Prompt

Generate a cpp solution to the following problem:

Сity N. has a huge problem with roads, food and IT-infrastructure. In total the city has n junctions, some pairs of them are connected by bidirectional roads. The road network consists of n - 1 roads, you can get from any junction to any other one by these roads. Yes, you're right — the road network forms an undirected tree.

Recently, the Mayor came up with a way that eliminates the problems with the food and the IT-infrastructure at the same time! He decided to put at the city junctions restaurants of two well-known cafe networks for IT professionals: "iMac D0naldz" and "Burger Bing". Since the network owners are not friends, it is strictly prohibited to place two restaurants of different networks on neighboring junctions. There are other requirements. Here's the full list:

  * each junction must have at most one restaurant; 
  * each restaurant belongs either to "iMac D0naldz", or to "Burger Bing"; 
  * each network should build at least one restaurant; 
  * there is no pair of junctions that are connected by a road and contains restaurants of different networks. 



The Mayor is going to take a large tax from each restaurant, so he is interested in making the total number of the restaurants as large as possible.

Help the Mayor to analyze the situation. Find all such pairs of (a, b) that a restaurants can belong to "iMac D0naldz", b restaurants can belong to "Burger Bing", and the sum of a + b is as large as possible.

Input

The first input line contains integer n (3 ≤ n ≤ 5000) — the number of junctions in the city. Next n - 1 lines list all roads one per line. Each road is given as a pair of integers xi, yi (1 ≤ xi, yi ≤ n) — the indexes of connected junctions. Consider the junctions indexed from 1 to n.

It is guaranteed that the given road network is represented by an undirected tree with n vertexes.

Output

Print on the first line integer z — the number of sought pairs. Then print all sought pairs (a, b) in the order of increasing of the first component a.

Examples

Input

5
1 2
2 3
3 4
4 5


Output

3
1 3
2 2
3 1


Input

10
1 2
2 3
3 4
5 6
6 7
7 4
8 9
9 10
10 4


Output

6
1 8
2 7
3 6
6 3
7 2
8 1

Note

The figure below shows the answers to the first test case. The junctions with "iMac D0naldz" restaurants are marked red and "Burger Bing" restaurants are marked blue.

<image>

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
class p445A {
 public:
  void solve() {
    long long n;
    cin >> n;
    unordered_map<long long, long long> cnt;
    long long mx = 0;
    for (int i = 0; i < n; i++) {
      long long a;
      cin >> a;
      mx = max(mx, a);
      cnt[a]++;
    }
    vector<long long> dp(mx + 1, 0);
    for (long long i = 1; i <= mx; i++) {
      dp[i] = max(dp[i], dp[i - 1]);
      if (!cnt.count(i)) continue;
      dp[i] = max(dp[i - 1], (i >= 2 ? dp[i - 2] : 0) + cnt[i] * i);
    }
    cout << dp[mx] << endl;
  }
};
class p550A {
 public:
  void solve() {
    string s;
    cin >> s;
    int l = -1;
    int cnt[2][2];
    memset(cnt, -1, sizeof(cnt));
    auto check = [&cnt](string &s, int flag) {
      for (int i = 0; i < s.size() - 1; i++) {
        if (s[i] == 'A' && s[i + 1] == 'B' && cnt[flag][0] == -1) {
          cnt[flag][0] = i + 1;
        }
        if (s[i] == 'B' && s[i + 1] == 'A' && cnt[flag][1] == -1) {
          cnt[flag][1] = i + 1;
        }
      }
    };
    check(s, 0);
    reverse(s.begin(), s.end());
    check(s, 1);
    if (cnt[0][1] != -1 && cnt[1][1] != -1 &&
        cnt[0][1] + 1 + cnt[1][1] + 1 <= s.size())
      cout << "YES" << endl;
    else if (cnt[0][0] != -1 && cnt[1][0] != -1 &&
             cnt[0][0] + 1 + cnt[1][0] + 1 <= s.size())
      cout << "YES" << endl;
    else
      cout << "NO" << endl;
  }
};
class p550C {
 public:
  void solve() {
    string s;
    cin >> s;
    int n = s.size();
    vector<vector<int>> dp(n + 1, vector<int>(8, 0));
    vector<vector<int>> pre(n + 1, vector<int>(8, -1));
    bool ok = false;
    for (int i = 1; i <= n; i++) {
      int ai = s[i - 1] - '0';
      dp[i][ai % 8] = 1;
      for (int j = 0; j < 8; j++) {
        if (dp[i - 1][j] == 1) {
          dp[i][(10 * j + ai) % 8] = 1;
          dp[i][j] = 1;
          pre[i][(10 * j + ai) % 8] = j;
          pre[i][j] = j;
        }
      }
      if (dp[i][0] == 1) ok = 1;
    }
    if (ok == 0)
      cout << "NO" << endl;
    else {
      cout << "YES" << endl;
      string ans;
      for (int i = 1; i <= n; i++) {
        if (dp[i][0] == 1) {
          int ci = i, cj = 0;
          while (ci > 0) {
            if (pre[ci][cj] == -1 || pre[ci][cj] != cj) {
              ans.append(1, s[ci - 1]);
            }
            if (pre[ci][cj] == -1) break;
            cj = pre[ci][cj];
            ci--;
          }
          reverse(ans.begin(), ans.end());
          cout << ans << endl;
          break;
        }
      }
    }
  }
};
class p545C {
 public:
  void solve() {
    int n;
    cin >> n;
    vector<pair<long long, long long>> tree;
    for (int i = 0; i < n; i++) {
      long long x, h;
      cin >> x >> h;
      tree.emplace_back(x, h);
    }
    if (n == 1)
      cout << 1 << endl;
    else {
      int res = 1;
      int pre = 0;
      for (int i = 1; i < n; i++) {
        if (pre == 0) {
          if (tree[i].first - tree[i].second > tree[i - 1].first) {
            res++;
          } else if (i == n - 1 ||
                     tree[i + 1].first > tree[i].first + tree[i].second) {
            pre = 1;
            res++;
          }
        } else {
          if (tree[i].first - tree[i].second >
              tree[i - 1].first + tree[i - 1].second) {
            pre = 0;
            res++;
          } else if (i == n - 1 ||
                     tree[i + 1].first > tree[i].first + tree[i].second) {
            pre = 1;
            res++;
          } else
            pre = 0;
        }
      }
      cout << res << endl;
    }
  }
};
class p166E {
 public:
  vector<vector<long long>> matrixmul(const vector<vector<long long>> &a,
                                      const vector<vector<long long>> &b) {
    int n = a.size();
    vector<vector<long long>> c(n, vector<long long>(n, 0));
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        for (int k = 0; k < n; k++) {
          c[i][j] += a[i][k] * b[k][j];
          c[i][j] %= 1000000007;
        }
      }
    }
    return c;
  }
  vector<vector<long long>> fmul(vector<vector<long long>> &matrix, int n) {
    vector<vector<long long>> res(matrix.size(),
                                  vector<long long>(matrix[0].size(), 0));
    for (int i = 0; i < matrix.size(); i++) res[i][i] = 1;
    while (n >= 1) {
      if (n & 1) {
        res = matrixmul(res, matrix);
      }
      n = n >> 1;
      matrix = matrixmul(matrix, matrix);
    }
    return res;
  }
  void solve() {
    int n;
    cin >> n;
    vector<vector<long long>> a(4, vector<long long>(4, 1));
    for (int i = 0; i < 4; i++) a[i][i] = 0;
    auto res = fmul(a, n);
    cout << res[3][3] << endl;
  }
};
class p676C {
 public:
  void solve() {
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    int a = 0, b = 0;
    int res = 0;
    for (int l = 0, r = 0; l < n; l++) {
      while (min(a, b) <= k && r < n) {
        res = max(res, a + b);
        if (s[r] == 'a')
          a++;
        else
          b++;
        r++;
      }
      if (min(a, b) <= k) res = max(res, a + b);
      if (s[l] == 'a')
        a--;
      else
        b--;
    }
    cout << res << endl;
  }
};
class p839C {
 public:
  double ans;
  vector<vector<int>> e;
  void dfs(int fa, int cur, double pre) {
    double pro = e[cur].size() <= 1
                     ? (fa == -1 ? pre : 0.0)
                     : pre / (fa == -1 ? e[cur].size() : (e[cur].size() - 1));
    for (int next : e[cur]) {
      if (next == fa) continue;
      ans += pro;
      dfs(cur, next, pro);
    }
  }
  void solve() {
    int n;
    cin >> n;
    e.clear();
    e = vector<vector<int>>(n);
    for (int i = 0; i < n - 1; i++) {
      int u, v;
      cin >> u >> v;
      u--;
      v--;
      e[u].push_back(v);
      e[v].push_back(u);
    }
    ans = 0.0;
    dfs(-1, 0, 1);
    printf("%.15lf\n", ans);
  }
};
class p1272D {
 public:
  void solve() {
    int n;
    cin >> n;
    vector<int> a(n, 0);
    for (int i = 0; i < n; i++) cin >> a[i];
    vector<int> l(n, 0), r(n, 0);
    l[0] = 1;
    for (int i = 1; i < n; i++) {
      l[i] = 1;
      if (a[i] > a[i - 1]) l[i] += l[i - 1];
    }
    r[n - 1] = 1;
    for (int i = n - 2; i >= 0; i--) {
      r[i] = 1;
      if (a[i] < a[i + 1]) r[i] += r[i + 1];
    }
    int res = 0;
    for (int i = 0; i < n; i++) {
      res = max(res, l[i]);
      if (i < n - 2 && a[i] < a[i + 2]) res = max(res, l[i] + r[i + 2]);
    }
    cout << res << endl;
  }
};
class p1253C {
 public:
  void solve() {
    long long m, n;
    cin >> n >> m;
    vector<long long> a(n, 0);
    for (int i = 0; i < n; i++) cin >> a[i];
    sort(a.begin(), a.end());
    vector<long long> res;
    vector<long long> sum(n + 1, 0);
    for (int i = 1; i <= n; i++) {
      sum[i] = sum[i - 1] + a[i - 1];
    }
    vector<long long> x(n + 1, 0);
    for (int i = 1; i <= n; i++) {
      x[i] = sum[i] + x[max(0ll, i - m)];
      res.push_back(x[i]);
    }
    for (auto i : res) cout << i << " ";
    cout << endl;
  }
};
class p1234C {
 public:
  void solve() {
    int q;
    cin >> q;
    for (int i = 0; i < q; i++) {
      vector<string> s(2);
      int n;
      cin >> n >> s[0] >> s[1];
      int row = 0, pos = 0;
      bool ok = true;
      for (pos = 0; pos < n; pos++) {
        if (s[row][pos] >= '3') {
          if (s[1 - row][pos] < '3') {
            ok = false;
            break;
          } else {
            row = 1 - row;
          }
        }
      }
      if (ok && row == 1 && pos == n)
        cout << "YES" << endl;
      else
        cout << "NO" << endl;
    }
  }
};
class p1307C {
 public:
  void solve() {
    string s;
    cin >> s;
    vector<long long> cnt(26, 0);
    vector<long long> dict(1000, 0);
    long long mx = 0;
    for (int i = 0; i < s.size(); i++) {
      for (int j = 0; j < 26; j++) {
        dict[j * 30 + s[i] - 'a'] += cnt[j];
        mx = max(mx, dict[j * 30 + s[i] - 'a']);
      }
      cnt[s[i] - 'a']++;
      mx = max(mx, cnt[s[i] - 'a']);
    }
    cout << mx << endl;
  }
};
class p1207C {
 public:
  void solve() {
    int t;
    cin >> t;
    while (t--) {
      long long n, a, b;
      cin >> n >> a >> b;
      string s;
      cin >> s;
      vector<vector<long long>> dp(n + 1, vector<long long>(2, -1));
      dp[0][0] = b;
      for (int i = 1; i <= n; i++) {
        if (s[i - 1] == '1') {
          if (dp[i - 1][1] != -1) dp[i][1] = dp[i - 1][1] + 2 * b + a;
          if (dp[i - 1][0] != -1)
            dp[i][1] = dp[i][1] != -1
                           ? min(dp[i][1], dp[i - 1][0] + 3 * (a + b) - a)
                           : dp[i - 1][0] + 3 * (a + b) - a;
        } else {
          if (dp[i - 1][1] != -1) dp[i][1] = dp[i - 1][1] + 2 * b + a;
          if (dp[i - 1][0] != -1)
            dp[i][1] = dp[i][1] != -1
                           ? min(dp[i][1], dp[i - 1][0] + 3 * (a + b) - a)
                           : dp[i - 1][0] + 3 * (a + b) - a;
          if (dp[i - 1][0] != -1) dp[i][0] = dp[i - 1][0] + a + b;
          if (dp[i - 1][1] != -1)
            dp[i][0] = dp[i][0] != -1 ? min(dp[i][0], dp[i - 1][1] + 2 * a + b)
                                      : dp[i - 1][1] + 2 * a + b;
        }
      }
      cout << dp[n][0] << endl;
    }
  }
};
class p1105C {
 public:
  void solve() {
    long long n, l, r;
    cin >> n >> l >> r;
    l--;
    long long zero = r / 3 - l / 3;
    long long one = (r + 2) / 3 - (l + 2) / 3;
    long long two = (r + 1) / 3 - (l + 1) / 3;
    vector<vector<long long>> dp(n, vector<long long>(3, 0));
    dp[0][0] = zero;
    dp[0][1] = one;
    dp[0][2] = two;
    for (int i = 1; i < n; i++) {
      dp[i][0] =
          (dp[i - 1][0] * zero + dp[i - 1][1] * two + dp[i - 1][2] * one) %
          1000000007;
      dp[i][1] =
          (dp[i - 1][0] * one + dp[i - 1][1] * zero + dp[i - 1][2] * two) %
          1000000007;
      dp[i][2] =
          (dp[i - 1][0] * two + dp[i - 1][1] * one + dp[i - 1][2] * zero) %
          1000000007;
    }
    cout << dp[n - 1][0] << endl;
  }
};
class p611C {
 public:
  void solve() {
    int h, w;
    cin >> h >> w;
    vector<string> g(h);
    for (int i = 0; i < h; i++) cin >> g[i];
    vector<vector<vector<int>>> dp(
        h + 1, vector<vector<int>>(w + 1, vector<int>(2, 0)));
    for (int i = 1; i <= h; i++) {
      for (int j = 1; j <= w; j++) {
        for (int k = 0; k < 2; k++)
          dp[i][j][k] = dp[i - 1][j][k] + dp[i][j - 1][k] - dp[i - 1][j - 1][k];
        if (g[i - 1][j - 1] == '#') {
          continue;
        }
        if (i >= 2 && g[i - 2][j - 1] == '.') dp[i][j][0]++;
        if (j >= 2 && g[i - 1][j - 2] == '.') dp[i][j][1]++;
      }
    }
    int q;
    cin >> q;
    for (int i = 1; i <= q; i++) {
      int r1, c1, r2, c2;
      cin >> r1 >> c1 >> r2 >> c2;
      int res = 0;
      res +=
          dp[r2][c2][0] - dp[r1][c2][0] - dp[r2][c1 - 1][0] + dp[r1][c1 - 1][0];
      res +=
          dp[r2][c2][1] - dp[r2][c1][1] - dp[r1 - 1][c2][1] + dp[r1 - 1][c1][1];
      cout << res << endl;
    }
  }
};
class p1051C {
 public:
  void solve() {
    int t, n = 0;
    cin >> t;
    vector<int> a(t, 0);
    for (auto &i : a) {
      cin >> i;
      n = max(n, i);
    }
    vector<int> cnt(n + 1, 0);
    vector<int> used(n + 1, -1);
    for (int i = 0; i < t; i++) {
      cnt[a[i]]++;
    }
    int odd = 0, even = 0;
    for (int i = 0; i <= n; i++) {
      if (cnt[i] == 1)
        odd++;
      else if (cnt[i] > 2)
        even++;
    }
    if (odd % 2 == 1 && even == 0) {
      cout << "NO" << endl;
      return;
    }
    if (odd % 2 == 1) {
      for (int i = 0; i <= n; i++)
        if (cnt[i] > 2) {
          cnt[i] = 1;
          break;
        }
    }
    cout << "YES" << endl;
    string s;
    char ch[2] = {'A', 'B'};
    int flag = 0;
    for (int i = 0; i < t; i++) {
      if (cnt[a[i]] != 1)
        s.append(1, 'A');
      else {
        if (used[a[i]] != -1)
          s.append(1, ch[used[a[i]] ^ 1]);
        else {
          used[a[i]] = flag;
          s.append(1, ch[flag]);
          flag ^= 1;
        }
      }
    }
    cout << s << endl;
  }
};
class p1313C1 {
 public:
  void solve() {
    int n;
    cin >> n;
    vector<long long> a(n, 0);
    for (auto &i : a) cin >> i;
    vector<vector<long long>> f(2, vector<long long>(n, 0));
    stack<int> left, right;
    auto monostack = [&n, &f](vector<long long> &a, stack<int> &left,
                              int flag) {
      for (int i = 0; i < n; i++) {
        while (left.size() != 0 && a[left.top()] > a[i]) left.pop();
        long long pre = left.size() == 0 ? 0 : f[flag][left.top()];
        long long len = left.size() == 0 ? i + 1 : i - left.top();
        f[flag][i] = pre + len * a[i];
        left.push(i);
      }
    };
    monostack(a, left, 0);
    reverse(a.begin(), a.end());
    monostack(a, right, 1);
    reverse(f[1].begin(), f[1].end());
    reverse(a.begin(), a.end());
    long long id = -1, mx = 0;
    for (int i = 0; i < n; i++) {
      if (f[0][i] + f[1][i] - a[i] > mx) {
        id = i;
        mx = f[0][i] + f[1][i] - a[i];
      }
    }
    vector<long long> res(n, 0);
    res[id] = a[id];
    for (long long i = id - 1; i >= 0; i--) {
      if (a[i] > res[i + 1])
        res[i] = res[i + 1];
      else
        res[i] = a[i];
    }
    for (long long i = id + 1; i < n; i++) {
      if (a[i] > res[i - 1])
        res[i] = res[i - 1];
      else
        res[i] = a[i];
    }
    for (long long i : res) cout << i << " ";
    cout << endl;
  }
};
class p982C {
 public:
  int ans = 0;
  vector<vector<int>> edge;
  int dfs(int cur, int fa) {
    int odd = 0;
    for (auto child : edge[cur]) {
      if (child == fa) continue;
      int temp = dfs(child, cur);
      if (temp == 0)
        ans++;
      else
        odd++;
    }
    if (odd % 2 == 1)
      return 0;
    else
      return 1;
  }
  void solve() {
    int n;
    cin >> n;
    ans = 0;
    edge = vector<vector<int>>(n);
    for (int i = 0; i < n - 1; i++) {
      int u, v;
      cin >> u >> v;
      u--;
      v--;
      edge[u].push_back(v);
      edge[v].push_back(u);
    }
    if (dfs(0, -1) != 0) {
      cout << -1 << endl;
    } else
      cout << ans << endl;
  }
};
class p891C {
 public:
  int gcd(int x, int y) {
    if (y == 0) return x;
    return gcd(y, x % y);
  }
  void solve() {
    int n;
    cin >> n;
    vector<int> a(n, 0);
    int cnt = 0;
    for (int i = 0; i < n; i++) {
      cin >> a[i];
      if (a[i] == 1) cnt++;
    }
    if (cnt > 0) {
      cout << n - cnt << endl;
      return;
    }
    bool ok = false;
    int len = n + 1;
    for (int l = 0; l < n; l++) {
      int temp = a[l];
      for (int r = l; r < n; r++) {
        temp = gcd(temp, a[r]);
        if (temp == 1) {
          len = min(len, r - l);
          break;
        }
      }
    }
    if (len == n + 1)
      cout << -1 << endl;
    else
      cout << len + n - 1 << endl;
  }
};
class p877B {
 public:
  void solve() {
    string s;
    cin >> s;
    int n = s.size();
    vector<vector<int>> a(2, vector<int>(n + 1, 0));
    for (int i = 0; i < s.size(); i++) {
      int cur = s[i] - 'a';
      a[0][i + 1] += a[0][i];
      a[1][i + 1] += a[1][i];
      a[cur][i + 1]++;
    }
    int res = 0;
    for (int i = 0; i <= n; i++) {
      for (int j = i; j <= n; j++) {
        int t1 = a[1][i];
        int t2 = a[0][j] - a[0][i];
        int t3 = a[1][n] - a[1][j];
        res = max(res, n - t1 - t2 - t3);
      }
    }
    cout << res << endl;
  }
};
class p1005D {
 public:
  void solve() {
    string s;
    cin >> s;
    int n = s.size();
    vector<int> dp(n + 1, 0);
    int sum = 0;
    unordered_map<int, int> cnt;
    cnt[0] = 0;
    int res = 0;
    for (int i = 1; i <= n; i++) {
      sum += (s[i - 1] - '0');
      sum %= 3;
      dp[i] = dp[i - 1];
      if (cnt.count((sum))) {
        dp[i] = max(dp[i], dp[cnt[sum]] + 1);
      }
      res = max(res, dp[i]);
      cnt[sum] = i;
    }
    cout << res << endl;
  }
};
class p264B {
 public:
  int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
  }
  void solve() {
    int n;
    cin >> n;
    vector<int> a(n, 0);
    for (auto &i : a) cin >> i;
    int res = 0;
    unordered_map<int, int> dp;
    for (int &i : a) {
      if (i == 1) {
        res = max(res, 1);
        continue;
      }
      vector<int> temp;
      int cur = 0;
      for (int j = 2; j <= i / j; j++) {
        if (i % j == 0) {
          temp.push_back(j);
          cur = max(cur, dp[j] + 1);
          while (i % j == 0) i /= j;
        }
      }
      if (i > 1) {
        temp.push_back(i);
        cur = max(cur, dp[i] + 1);
      }
      for (int j : temp) dp[j] = max(dp[j], cur);
      res = max(cur, res);
    }
    cout << res << endl;
  }
};
class p553A {
 public:
  void solve() {
    int k;
    cin >> k;
    vector<long long> a(k, 0);
    vector<long long> dp(k, 0);
    int maxn = 1010;
    vector<vector<long long>> f(maxn, vector<long long>(maxn, 0));
    f[0][0] = 1;
    for (int i = 1; i < maxn; i++) {
      f[i][0] = 1;
      for (int j = 1; j <= i; j++) {
        f[i][j] = (f[i - 1][j] + f[i - 1][j - 1]) % 1000000007;
      }
    }
    for (auto &i : a) cin >> i;
    long long sum = a[0];
    dp[0] = 1;
    for (long long i = 1; i < k; i++) {
      sum += a[i] - 1;
      dp[i] = (dp[i - 1] * f[sum][a[i] - 1]) % 1000000007;
      sum++;
    }
    cout << dp.back() % 1000000007 << endl;
  }
};
class p322B {
 public:
  void solve() {
    int n, k;
    cin >> n >> k;
    vector<long long> v(n, 0);
    vector<long long> sum(n + 1, 0);
    vector<long long> dp(n + 1, 0);
    vector<long long> index(n + 1, 0);
    dp[0] = 0;
    index[0] = 0;
    long long res = 0;
    for (int i = 1; i <= n; i++) {
      cin >> v[i - 1];
      sum[i] += sum[i - 1] + v[i - 1];
      dp[i] = dp[i - 1];
      index[i] = index[i - 1];
      if (i >= k) {
        if (sum[i] - sum[i - k] > dp[i]) {
          dp[i] = sum[i] - sum[i - k];
          index[i] = i - k + 1;
        }
        res = max(res, sum[i] - sum[i - k] + dp[i - k]);
      }
    }
    vector<pair<long long, long long>> ans;
    for (int i = 1; i <= n; i++) {
      if (i >= k) {
        if (res == dp[i - k] + sum[i] - sum[i - k]) {
          ans.emplace_back(index[i - k], i - k + 1);
        }
      }
    }
    sort(ans.begin(), ans.end());
    cout << ans.begin()->first << " " << ans.begin()->second << endl;
  }
};
class p1084C {
 public:
  void solve() {
    string s;
    cin >> s;
    int n = s.size();
    vector<long long> a;
    long long sum = 0;
    for (int i = 1; i <= n; i++) {
      if (s[i - 1] == 'a') {
        sum++;
      } else if (s[i - 1] == 'b') {
        a.push_back(sum);
        sum = 0;
      }
    }
    if (sum != 0) a.push_back(sum);
    long long res = 1;
    if (a.size() == 0) {
      cout << 0 << endl;
      return;
    }
    for (auto i : a) {
      res = (res * (i + 1)) % 1000000007;
    }
    res = (res - 1 + 1000000007) % 1000000007;
    cout << res << endl;
  }
};
class p991D {
 public:
  void solve() {
    vector<string> a(2);
    cin >> a[0] >> a[1];
    int n = a[0].size();
    if (n == 1) {
      cout << 0 << endl;
      return;
    }
    vector<vector<int>> dp(n + 1, vector<int>(3, 0));
    vector<int> v(n, 0);
    for (int i = 0; i < n; i++) {
      if (a[0][i] == '0') v[i]++;
      if (a[1][i] == '0') v[i]++;
    }
    for (int i = 2; i <= n; i++) {
      dp[i][2] = max(dp[i - 1][0], max(dp[i - 1][1], dp[i - 1][2]));
      if (v[i - 1] == 0) continue;
      int pre = max(dp[i - 2][0], max(dp[i - 2][1], dp[i - 2][2]));
      if (v[i - 1] == 2) {
        if (v[i - 2] > 0) {
          if (v[i - 2] == 2) {
            dp[i][0] = max(dp[i][0], pre + 1);
            dp[i][1] = max(dp[i][1], pre + 1);
            dp[i][1] = max(dp[i][1], max(dp[i - 1][0], dp[i - 1][2]) + 1);
          } else
            dp[i][1] = max(dp[i][1], dp[i - 1][2] + 1);
        }
      } else {
        if (v[i - 2] == 2) {
          dp[i][0] = max(dp[i][0], pre + 1);
        }
      }
    }
    cout << max(dp[n][0], max(dp[n][1], dp[n][2])) << endl;
  }
};
class p855B {
 public:
  void solve() {
    long long n;
    cin >> n;
    vector<long long> v(3, 0);
    cin >> v[0] >> v[1] >> v[2];
    vector<long long> a(n, 0);
    for (auto &i : a) cin >> i;
    vector<vector<long long>> dp(n, vector<long long>(3, 0));
    dp[0][0] = v[0] * a[0];
    dp[0][1] = v[0] * a[0] + v[1] * a[0];
    dp[0][2] = v[0] * a[0] + v[1] * a[0] + v[2] * a[0];
    for (int i = 1; i < n; i++) {
      for (int j = 0; j < 3; j++) {
        dp[i][j] = dp[i - 1][j];
        long long temp = 0;
        for (int k = j; k >= 0; k--) {
          temp += v[k] * a[i];
          dp[i][j] = max(dp[i][j], temp + (k - 1 >= 0 ? dp[i - 1][k - 1] : 0));
        }
      }
    }
    cout << dp[n - 1][2] << endl;
  }
};
class p873B {
 public:
  void solve() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    unordered_map<int, int> cnt;
    int zero = 0, one = 0;
    int res = 0;
    cnt[0] = -1;
    for (int i = 0; i < n; i++) {
      if (s[i] == '0')
        zero++;
      else
        one++;
      int diff = zero - one;
      if (cnt.count(diff)) {
        res = max(res, i - cnt[diff]);
      } else
        cnt[diff] = i;
    }
    cout << res << endl;
  }
};
class p340D {
 public:
  void solve() {
    int n;
    cin >> n;
    vector<int> a(n, 0);
    for (auto &i : a) cin >> i;
    vector<int> dp;
    for (int i : a) {
      auto pos = upper_bound(dp.begin(), dp.end(), i) - dp.begin();
      if (pos == dp.size())
        dp.push_back(i);
      else
        dp[pos] = i;
    }
    cout << dp.size() << endl;
  }
};
class p1081C {
 public:
  void solve() {
    long long n, m, k;
    cin >> n >> m >> k;
    vector<vector<long long>> dp(n, vector<long long>(k + 1, 0));
    long long modulo = 998244353;
    dp[0][0] = m;
    for (int i = 1; i < n; i++) {
      for (int j = k; j >= 0; j--) {
        dp[i][j] =
            (dp[i - 1][j] + (j > 0 ? dp[i - 1][j - 1] : 0) * (m - 1)) % modulo;
      }
    }
    cout << dp[n - 1][k] << endl;
  }
};
class p761C {
 public:
  void solve() {
    int n, m;
    cin >> n >> m;
    vector<string> v(n);
    for (int i = 0; i < n; i++) cin >> v[i];
    vector<vector<int>> a(n, vector<int>(3, -1));
    auto check = [](char c) {
      if (c == '#' || c == '*' || c == '&') return true;
      return false;
    };
    for (int i = 0; i < n; i++) {
      for (int j = m - 1; j >= 0; j--) {
        if (isdigit(v[i][j]))
          a[i][0] = a[i][0] == -1 ? min(j, m - j) : min(a[i][0], min(j, m - j));
        if (isalpha(v[i][j]))
          a[i][1] = a[i][1] == -1 ? min(j, m - j) : min(a[i][1], min(j, m - j));
        if (check(v[i][j]))
          a[i][2] = a[i][2] == -1 ? min(j, m - j) : min(a[i][2], min(j, m - j));
      }
    }
    vector<vector<int>> dp(n + 1, vector<int>(1 << 3, 10000));
    dp[0][0] = 0;
    for (int i = 1; i <= n; i++) {
      dp[i][0] = dp[i - 1][0];
      for (int j = 1; j < (1 << 3); j++) {
        dp[i][j] = dp[i - 1][j];
        for (int k = 0; k < 3; k++) {
          if (((1 << k) & j) != 0 && a[i - 1][k] != -1) {
            int pre = (1 << k) ^ j;
            dp[i][j] = min(dp[i][j], dp[i - 1][pre] + a[i - 1][k]);
          }
        }
      }
    }
    cout << dp[n][(1 << 3) - 1] << endl;
  }
};
class p858C {
 public:
  void solve() {
    string s;
    cin >> s;
    unordered_set<char> dict{'a', 'e', 'i', 'o', 'u'};
    int block = 0, kind = 0;
    vector<char> res;
    bool first = 1;
    for (int i = 0; i < s.size(); i++) {
      if (!dict.count(s[i])) {
        block++;
        if (block > 2 && (s[i] != s[i - 1] || s[i - 1] != s[i - 2])) {
          res.push_back(' ');
          block = 1;
        }
      } else {
        block = kind = 0;
      }
      res.push_back(s[i]);
    }
    for (auto i : res) cout << i;
    cout << endl;
  }
};
class p204A {
 public:
  long long getTen(int x) {
    if (x == 0) return 1;
    long long temp = getTen(x / 2);
    if (x % 2 == 1) return temp * temp * 10;
    return temp * temp;
  }
  long long getDig(long long x) {
    if (x <= 0) return 0;
    if (x <= 9) return x;
    long long res = 0;
    vector<long long> a;
    while (x > 0) {
      a.emplace_back(x % 10);
      x /= 10;
    }
    reverse(a.begin(), a.end());
    int n = a.size();
    for (int i = 0; i < n; i++) {
      long long temp = getTen(max(0, n - 2 - (i + 1) + 1));
      int up = i > 0 ? 10 : a[i];
      for (int j = 1; j < up; j++) {
        res += temp;
      }
    }
    long long temp = 0;
    for (int i = 1; i < n - 1; i++) temp = temp * 10 + a[i];
    if (a.front() <= a.back()) temp++;
    res += temp;
    return res;
  }
  void solve() {
    long long l, r;
    cin >> l >> r;
    cout << getDig(r) - getDig(l - 1) << endl;
  }
};
class p859C {
 public:
  void solve() {
    int n;
    cin >> n;
    vector<int> a(n, 0);
    for (auto &i : a) cin >> i;
    vector<int> dp(n, 0);
    vector<int> sum(n, 0);
    sum[n - 1] = a[n - 1];
    dp[n - 1] = a[n - 1];
    for (int i = n - 2; i >= 0; i--) sum[i] = sum[i + 1] + a[i];
    for (int i = n - 2; i >= 0; i--) {
      dp[i] = max(dp[i + 1], sum[i + 1] - dp[i + 1] + a[i]);
    }
    cout << sum[0] - dp[0] << " " << dp[0] << endl;
  }
};
class p159D {
 public:
  void solve() {
    string s;
    cin >> s;
    long long n = s.size();
    vector<vector<long long>> done(n, vector<long long>(n, 0));
    vector<long long> dp(n, 0);
    vector<long long> sum(n, 0);
    auto check = [&s, &done, &n](int l, int r) {
      while (l >= 0 && r < n && s[l] == s[r]) {
        done[l][r] = 1;
        l--;
        r++;
      }
    };
    for (int i = 0; i < n; i++) {
      int l = i, r = i;
      check(l, r);
      l = i, r = i + 1;
      check(l, r);
    }
    dp[0] = 0;
    sum[0] = 1;
    for (int i = 1; i < n; i++) {
      long long cnt = 0, cur = 0;
      for (int j = 0; j <= i; j++) {
        if (done[j][i]) {
          cnt++;
          cur += j == 0 ? 0 : sum[j - 1];
        }
      }
      dp[i] = dp[i - 1] + cur;
      sum[i] = sum[i - 1] + cnt;
    }
    cout << dp[n - 1] << endl;
  }
};
class p255C {
 public:
  void solve() {
    int n;
    cin >> n;
    vector<int> a(n, 0);
    unordered_map<int, vector<int>> cnt;
    for (int i = 0; i < n; i++) {
      cin >> a[i];
      cnt[a[i]].push_back(i);
    }
    vector<int> v;
    int res = 0;
    for (auto it : cnt) {
      v.push_back(it.first);
      res = max(res, (int)it.second.size());
    }
    int sz = v.size();
    auto check = [&cnt, &v](int a, int b) {
      int res = 0;
      int i = 0, j = 0, lena = cnt[v[a]].size(), lenb = cnt[v[b]].size();
      while (i < lena && j < lenb) {
        if (cnt[v[a]][i] < cnt[v[b]][j]) {
          while (i < lena && cnt[v[a]][i] < cnt[v[b]][j]) i++;
          if (i < lena) res++;
        } else {
          while (j < lenb && cnt[v[b]][j] < cnt[v[a]][i]) j++;
          if (j < lenb) res++;
        }
      }
      return res + 2;
    };
    for (int i = 0; i < sz; i++) {
      for (int j = i + 1; j < sz; j++) {
        res = max(res, check(i, j));
      }
    }
    cout << res << endl;
  }
  void solve2() {
    int n;
    cin >> n;
    vector<int> a(n, 0);
    for (int i = 0; i < n; i++) cin >> a[i];
    vector<vector<int>> dp(n, vector<int>(n, 0));
    int res = 1;
    for (int i = 1; i < n; i++) {
      int k = -1;
      for (int j = 0; j < i; j++) {
        if (k == -1)
          dp[i][j] = 2;
        else
          dp[i][j] = dp[j][k] + 1;
        if (a[i] == a[j]) k = j;
        res = max(res, dp[i][j]);
      }
    }
    cout << res << endl;
  }
};
class p868C {
 public:
  void solve() {
    int n, k;
    cin >> n >> k;
    unordered_map<int, int> cnt;
    for (int i = 0; i < n; i++) {
      int mask = 0;
      for (int j = 0; j < k; j++) {
        int t = 0;
        cin >> t;
        if (t == 1) mask |= (1 << j);
      }
      cnt[mask]++;
    }
    bool flag = false;
    for (int i = 0; i < (1 << k); i++) {
      for (int j = 0; j < (1 << k); j++) {
        if ((i & j) == 0 && (cnt[i] && cnt[j])) flag = true;
      }
    }
    if (flag)
      cout << "YES" << endl;
    else
      cout << "NO" << endl;
  }
};
class p22B {
 public:
  void solve() {
    int n, m;
    cin >> n >> m;
    vector<string> a(n);
    vector<vector<int>> up(n, vector<int>(m, 0));
    vector<vector<int>> left(n, vector<int>(m, 0));
    for (int i = 0; i < n; i++) {
      cin >> a[i];
      for (int j = 0; j < m; j++) {
        if (a[i][j] == '0') {
          up[i][j] = left[i][j] = 1;
          if (i - 1 >= 0) up[i][j] += up[i - 1][j];
          if (j > 0) left[i][j] += left[i][j - 1];
        }
      }
    }
    int res = 0;
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        if (a[i][j] == '1') continue;
        int len = 1000000;
        for (int k = 1; k <= up[i][j]; k++) {
          len = min(len, left[i - k + 1][j]);
          res = max(res, (len + k) * 2);
        }
      }
    }
    cout << res << endl;
  }
};
class p566F {
 public:
  void solve() {
    int n;
    cin >> n;
    vector<int> a(n, 0);
    unordered_map<int, int> cnt;
    int mx = -1;
    for (int i = 0; i < n; i++) {
      cin >> a[i];
      mx = max(mx, a[i]);
    }
    vector<int> dp(mx + 1, 1);
    for (int i = 0; i < n; i++) {
      for (int j = 2 * a[i]; j <= mx; j += a[i]) {
        dp[j] = max(dp[j], dp[a[i]] + 1);
      }
    }
    int res = 0;
    for (int i = 0; i < n; i++) res = max(res, dp[a[i]]);
    cout << res << endl;
  }
};
class p191A {
 public:
  void solve() {
    int n;
    cin >> n;
    vector<string> s(n);
    vector<vector<int>> dp(26, vector<int>(26, -1));
    for (int i = 0; i < n; i++) cin >> s[i];
    int res = 0;
    for (int i = 0; i < n; i++) {
      int st = s[i].front() - 'a', ed = s[i].back() - 'a';
      for (int j = 0; j < 26; j++) {
        if (dp[j][st] != -1) {
          dp[j][ed] = max(dp[j][ed], dp[j][st] + (int)s[i].size());
        }
      }
      dp[st][ed] = max(dp[st][ed], (int)s[i].size());
    }
    for (int i = 0; i < 26; i++) res = max(res, dp[i][i]);
    cout << res << endl;
  }
};
class p417A {
 public:
  void solve() {
    int c, d, n, m, k;
    cin >> c >> d >> n >> m >> k;
    int res = 100000000;
    int remain = max(0, n * m - k);
    if (remain == 0) {
      cout << 0 << endl;
      return;
    }
    for (int i = 0; i * n <= remain + n - 1; i++) {
      int left = max(0, remain - i * n);
      res = min(res, i * c + left * d);
    }
    cout << res << endl;
  }
};
class p10B {
 public:
  void solve() {
    int n, k, m;
    cin >> n >> k;
    vector<vector<vector<int>>> dp(
        k + 1, vector<vector<int>>(k + 1, vector<int>(k + 1, 0x3f3f3f3f)));
    for (int i = 1; i <= k; i++) {
      for (int j = 1; j <= k; j++) {
        dp[i][j][0] = 0;
        for (int r = 1; r + j - 1 <= k; r++) {
          dp[i][j][r] = dp[i][j][r - 1] + abs(i - (k + 1) / 2) +
                        abs(j + r - 1 - (k + 1) / 2);
        }
      }
    }
    while (n--) {
      cin >> m;
      int ans = 0x3f3f3f3f, x, l, r;
      for (int i = 1; i <= k; i++) {
        for (int j = 1; j <= k; j++) {
          if (dp[i][j][m] < ans) {
            x = i;
            l = j;
            r = j + m - 1;
            ans = dp[i][j][m];
          }
        }
      }
      if (ans == 0x3f3f3f3f)
        cout << -1 << endl;
      else {
        cout << x << " " << l << " " << r << endl;
        for (int i = 1; i <= k; i++) {
          for (int j = 1; j + i - 1 <= k; j++) {
            if (!(i + j - 1 < l || i > r)) {
              dp[x][i][j] = 0x3f3f3f3f;
            }
          }
        }
      }
    }
  }
};
class p74B {
 public:
  void solve() {
    int n, m, k;
    cin >> n >> m >> k;
    string to, dir;
    cin >> to >> dir;
    int d = 0;
    string t;
    cin >> t;
    if (dir == "head")
      d = -1;
    else
      d = 1;
    int res = 0;
    bool win = true;
    auto move = [&k, &d, &n]() {
      k += d;
      if (k == 0)
        k = 2, d = -d;
      else if (k == n + 1)
        k = n - 1, d = -d;
    };
    for (int i = 0; i < t.size(); i++) {
      if (t[i] == '0') {
        if ((m - k) * d >= 0)
          m += d;
        else
          m -= d;
        if (m == 0) m = 1;
        if (m == n + 1) m = n;
        if (m == k) {
          win = false, res = i;
          break;
        }
        move();
      } else {
        move();
        if (d == -1) {
          m = (k == n ? 1 : n);
        } else
          m = (k == 1 ? n : 1);
      }
      if (m == k) {
        win = false, res = i;
        break;
      }
    }
    if (win)
      cout << "Stowaway" << endl;
    else {
      cout << "Controller " << res + 1 << endl;
    }
  }
};
class p212E {
 public:
  int n;
  int res[50005];
  vector<vector<int>> e;
  int dfs(int cur, int fa) {
    int cnt = 1;
    vector<int> sub;
    for (auto c : e[cur]) {
      if (c == fa) continue;
      auto temp = dfs(c, cur);
      sub.push_back(temp);
      cnt += temp;
    }
    if (cnt == 1) return cnt;
    if (n - cnt != 0) sub.push_back(n - cnt);
    vector<vector<bool>> dp =
        vector<vector<bool>>(sub.size() + 1, vector<bool>(n + 1, 0));
    dp[0][0] = 1;
    for (int j = 1; j <= sub.size(); j++) {
      for (int i = 1; i < n - 1; i++) {
        dp[j][i] = dp[j - 1][i];
        if (i >= sub[j - 1] && dp[j - 1][i - sub[j - 1]]) dp[j][i] = 1;
        if (dp[j][i]) {
          res[i] = res[n - 1 - i] = 1;
        }
      }
    }
    return cnt;
  }
  void solve() {
    cin >> n;
    memset(res, 0, sizeof(res));
    e = vector<vector<int>>(n + 1);
    for (int i = 0; i < n - 1; i++) {
      int x, y;
      cin >> x >> y;
      e[x].push_back(y);
      e[y].push_back(x);
    }
    dfs(1, 0);
    vector<pair<long long, long long>> cnt;
    for (int i = 1; i < n - 1; i++) {
      if (res[i] == 1) cnt.emplace_back(i, n - 1 - i);
    }
    cout << cnt.size() << endl;
    for (auto i : cnt) cout << i.first << " " << i.second << endl;
  }
};
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  p212E ans;
  ans.solve();
  return 0;
}

```