Problem: Takahashi has decided to make a Christmas Tree for the Christmas party in AtCoder, Inc.

A Christmas Tree is a tree with N vertices numbered 1 through N and N-1 edges, whose i-th edge (1\leq i\leq N-1) connects Vertex a_i and b_i.

He would like to make one as follows:

* Specify two non-negative integers A and B.
* Prepare A Christmas Paths whose lengths are at most B. Here, a Christmas Path of length X is a graph with X+1 vertices and X edges such that, if we properly number the vertices 1 through X+1, the i-th edge (1\leq i\leq X) will connect Vertex i and i+1.
* Repeat the following operation until he has one connected tree:
* Select two vertices x and y that belong to different connected components. Combine x and y into one vertex. More precisely, for each edge (p,y) incident to the vertex y, add the edge (p,x). Then, delete the vertex y and all the edges incident to y.
* Properly number the vertices in the tree.



Takahashi would like to find the lexicographically smallest pair (A,B) such that he can make a Christmas Tree, that is, find the smallest A, and find the smallest B under the condition that A is minimized.

Solve this problem for him.

Constraints

* 2 \leq N \leq 10^5
* 1 \leq a_i,b_i \leq N
* The given graph is a tree.

Input

Input is given from Standard Input in the following format:


N
a_1 b_1
:
a_{N-1} b_{N-1}


Output

For the lexicographically smallest (A,B), print A and B with a space in between.

Examples

Input

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


Output

3 2


Input

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


Output

2 5


Input

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


Output

3 4

Solution (in CPP):

Solution:
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
const int MAXN = 1e5 + 10;

struct Edge {
  int v, next;
}edge[MAXN << 1];
int head[MAXN], tail, n, deg[MAXN];
void insert(int u, int v) {
  edge[++tail] = (Edge) {v, head[u]}; head[u] = tail;
}
namespace solver1 {
  int f[MAXN];
  int bound, root;
  bool dfs(int u, int fa) {
    std::vector <int> dps;
    for (int i = head[u]; i; i = edge[i].next) {
      int v = edge[i].v;
      if (v == fa) continue;
      if (!dfs(v, u)) return 0;
      if (f[v] > bound) return 0;
      dps.push_back(f[v]);
    }
    if (deg[u] & 1) dps.push_back(0);
    std::sort(dps.begin(), dps.end());
    int l = 0, r = dps.size() - 1;
    while(l <= r) {
      int mid = (l + r) >> 1;
      bool flag = 1;
      for (int i = 0, j = dps.size() - 1; i < j; i++, j--) {
        if (i == mid) i++;
        if (j == mid) j--;
        if (dps[i] + dps[j] > bound) {flag = 0; break;}
      } 
      if (flag) {
        f[u] = dps[mid];
        r = mid - 1;
      } else {
        l = mid + 1;
      }
    }
    f[u]++;
    return f[u];
  }
  bool check() {
    memset(f, -1, sizeof f);
    return dfs(root, 0) 
      && f[root] <= bound + 1;
  }
  void main() {
    int ans1 = 0;
    for (int i = 1; i <= n; i++) { 
      if (deg[i] & 1) ans1++, root = i; 
    }
    ans1 /= 2;
    printf("%d ", ans1);
    int l = 1, r = n, ans2 = 0;
    deg[root]++;
    while (l <= r) {
      int mid = (l + r) >> 1;
      bound = mid;
      if (check()) {
        ans2 = mid;
        r = mid - 1;
      } else {
        l = mid + 1;
      }
    }
    printf("%d\n", ans2);
  }
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i < n; i++) {
    int a, b;
    scanf("%d%d", &a, &b);
    insert(a, b);
    insert(b, a);
    deg[a]++; deg[b]++;
  }
  solver1::main();
}