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;
int recur_depth = 0;
template <typename Ostream, typename Cont>
typename enable_if<is_same<Ostream, ostream>::value, Ostream&>::type operator<<(
    Ostream& os, const Cont& v) {
  os << "[";
  for (auto& x : v) {
    os << x << ", ";
  }
  return os << "]";
}
template <typename Ostream, typename... Ts>
Ostream& operator<<(Ostream& os, const pair<Ts...>& p) {
  return os << "{" << p.first << ", " << p.second << "}";
}
const long long mod = (long long)1e9 + 7;
long long power(long long x, long long y, long long p) {
  long long res = 1;
  x = x % p;
  if (x == 0) return 0;
  while (y > 0) {
    if (y & 1) res = (res * x) % p;
    y = y >> 1;
    x = (x * x) % p;
  }
  return res;
}
long long extend_gcd(long long a, long long b, long long& x, long long& y) {
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  }
  long long x1, y1;
  long long d = extend_gcd(b, a % b, x1, y1);
  x = y1;
  y = x1 - y1 * (a / b);
  return d;
}
long long modinv(long long a, long long p) { return power(a, p - 2, p); }
long long rowNum[] = {-1, 0, 0, 1};
long long colNum[] = {0, -1, 1, 0};
std::vector<int> v[(long long)2e5 + 9];
std::vector<int> vis((long long)2e5 + 9);
std::vector<int> dis((long long)2e5 + 9);
std::vector<int> deg((long long)2e5 + 9);
void dfs(int i) {
  vis[i] = 1;
  for (auto x : v[i]) {
    if (!vis[x]) {
      dis[x] = dis[i] + 1;
      dfs(x);
    }
  }
}
int check(int i) {
  int cnt = 0;
  for (auto x : v[i]) {
    for (auto y : v[x]) {
      vis[y] = 1;
      if (y != i && deg[y] == 1) cnt++;
    }
  }
  return cnt;
}
signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n;
  cin >> n;
  for (int i = 0; i < n - 1; i++) {
    int a, b;
    cin >> a >> b;
    v[a].push_back(b);
    v[b].push_back(a);
    deg[a]++;
    deg[b]++;
  }
  dfs(1);
  for (int i = 1; i <= n; i++) vis[i] = 0;
  int iseven = 0, isodd = 0, diff = 0;
  for (int i = 1; i <= n; i++) {
    if (deg[i] == 1) {
      if (dis[i] % 2 == 0)
        iseven = 1;
      else
        isodd = 1;
      if (!vis[i]) diff += check(i);
    }
  }
  int mnans = 1, mxans = n - 1;
  if (iseven && isodd) mnans = 3;
  ;
  mxans = mxans - diff;
  cout << mnans << " " << mxans << endl;
}
