You have unweighted tree of n vertices. You have to assign a positive weight to each edge so that the following condition would hold:

  * For every two different leaves v_{1} and v_{2} of this tree, [bitwise XOR](https://en.wikipedia.org/wiki/Bitwise_operation#XOR) of weights of all edges on the simple path between v_{1} and v_{2} has to be equal to 0. 



Note that you can put very large positive integers (like 10^{(10^{10})}).

It's guaranteed that such assignment always exists under given constraints. Now let's define f as the number of distinct weights in assignment.

<image> In this example, assignment is valid, because bitwise XOR of all edge weights between every pair of leaves is 0. f value is 2 here, because there are 2 distinct edge weights(4 and 5).

<image> In this example, assignment is invalid, because bitwise XOR of all edge weights between vertex 1 and vertex 6 (3, 4, 5, 4) is not 0. 

What are the minimum and the maximum possible values of f for the given tree? Find and print both.

Input

The first line contains integer n (3 ≤ n ≤ 10^{5}) — the number of vertices in given tree.

The i-th of the next n-1 lines contains two integers a_{i} and b_{i} (1 ≤ a_{i} < b_{i} ≤ n) — it means there is an edge between a_{i} and b_{i}. It is guaranteed that given graph forms tree of n vertices.

Output

Print two integers — the minimum and maximum possible value of f can be made from valid assignment of given tree. Note that it's always possible to make an assignment under given constraints.

Examples

Input


6
1 3
2 3
3 4
4 5
5 6


Output


1 4


Input


6
1 3
2 3
3 4
4 5
4 6


Output


3 3


Input


7
1 2
2 7
3 4
4 7
5 6
6 7


Output


1 6

Note

In the first example, possible assignments for each minimum and maximum are described in picture below. Of course, there are multiple possible assignments for each minimum and maximum. 

<image>

In the second example, possible assignments for each minimum and maximum are described in picture below. The f value of valid assignment of this tree is always 3. 

<image>

In the third example, possible assignments for each minimum and maximum are described in picture below. Of course, there are multiple possible assignments for each minimum and maximum. 

<image>
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using namespace std;
template <typename T>
inline bool read(T& ret) {
  T x = 0, f = 1;
  char ch = getchar();
  while (ch != EOF && (ch > '9' || ch < '0')) {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  if (EOF == ch) return false;
  do x = x * 10 + ch - 48, ch = getchar();
  while (ch >= '0' && ch <= '9');
  ret = x * f;
  return true;
}
inline char nc() {
  static char buf[100000], *p1 = buf, *p2 = buf;
  return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
             ? EOF
             : *p1++;
}
template <typename T>
bool rn(T& v) {
  static char ch;
  while (ch != EOF && !isdigit(ch)) ch = nc();
  if (ch == EOF) return false;
  for (v = 0; isdigit(ch); ch = nc()) v = v * 10 + ch - '0';
  return true;
}
template <typename T>
void o(T p) {
  static int stk[70], tp;
  if (p == 0) {
    putchar('0');
    return;
  }
  if (p < 0) {
    p = -p;
    putchar('-');
  }
  while (p) stk[++tp] = p % 10, p /= 10;
  while (tp) putchar(stk[tp--] + '0');
}
LL bin(LL x, LL n, LL MOD) {
  LL ret = MOD != 1;
  for (x %= MOD; n; n >>= 1, x = x * x % MOD)
    if (n & 1) ret = ret * x % MOD;
  return ret;
}
inline LL get_inv(LL x, LL p) { return bin(x, p - 2, p); }
void DFS(map<int, set<int>>& tree, map<int, int>& vis, int a, int di) {
  vis[a] = di;
  auto& x = tree[a];
  for (auto& nxt : x) {
    if (vis.end() != vis.find(nxt)) continue;
    DFS(tree, vis, nxt, di + 1);
  }
}
void Solve() {
  map<int, set<int>> tree;
  set<int> leafs;
  set<int> parts;
  int a, b, n;
  read(n);
  for (int i = 0; i < n; i++) {
    read(a);
    read(b);
    tree[a].insert(b);
    tree[b].insert(a);
  }
  for (auto& node : tree) {
    if (node.second.size() == 1) {
      leafs.insert(node.first);
      parts.insert(*node.second.begin());
    }
  }
  int maxv = n - 1 - leafs.size() + parts.size();
  map<int, int> vis;
  DFS(tree, vis, a, 0);
  int minv = 3;
  int cnt[2] = {0, 0};
  for (auto l : leafs) {
    cnt[vis[l] % 2]++;
  }
  if (cnt[0] == leafs.size() || cnt[1] == leafs.size()) {
    minv = 1;
  }
  printf("%d %d\n", minv, maxv);
}
int main() {
  Solve();
  return 0;
  return 0;
}
