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 <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<ll> vll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<vector<ll>> vvll;
const ll inf = 1e16;
const ll md = 1000000007;
vi to[100005];
int deg[100005];
vi par;
int dp0[100005];
int dp[100005];
vi dp_uu;
int n;

int dfs(int u, int ou) {
  par[u] = ou;
  int to_leaf = 0;
  for (int ku : to[u]) {
    if (ku == ou) continue;
    to_leaf = dfs(ku, u) + 1;
  }
  if (to_leaf >= 0) {
    if (deg[ou] == 2 && ou != 0)
      return to_leaf;
    else {
      dp0[u] = to_leaf;
      return -10;
    }
  }
  dp_uu.push_back(u);
  return -10;
}

bool check(int m) {
  rep(i, n) dp[i] = dp0[i];
  //cout << "m=" << m << endl;
  for (int u : dp_uu) {
    vi dists(0);
    for (int ku : to[u]) {
      if (ku == par[u]) continue;
      dists.push_back(dp[ku] + 1);
    }
    sort(dists.begin(), dists.end());
    //cout << "u=" << u << endl;
    //for (int d : dists) cout << d << " ";
    //cout << endl;
    int n_child = dists.size();
    if (dists[n_child - 1] > m) return false;

    //cout << n_child << " " << (n_child & 1) << endl;
    if ((n_child & 1) == 0) {
      bool success = true;
      rep(i, n_child / 2) if (dists[i] + dists[n_child - 1 - i] > m) {
        //cout << "fail" << dists[i] << " " << dists[n_child - 1 - i] << endl;
        n_child--;
        success = false;
        break;
      }
      if (success) {
        dp[u] = 0;
        continue;
      }
    }

    int l = -1, r = n_child;
    while (l + 1 < r) {
      int c = (l + r) / 2;
      int i = 0, j = n_child - 1;
      bool ok = true;
      rep(_, n_child / 2) {
        if (i == c) i++;
        if (j == c) j--;
        if (dists[i] + dists[j] > m) {
          if (c == n_child - 1) return false;
          ok = false;
          break;
        }
        i++;
        j--;
      }
      if (ok)
        r = c;
      else
        l = c;
    }
    dp[u] = dists[r];
  }
  if ((deg[0] & 1) == 0 && dp[0] > 0) return false;
  return true;
}

int main() {
  cin >> n;
  par.resize(n, -1);
  rep(i, n - 1) {
    int a, b;
    cin >> a >> b;
    a--;
    b--;
    to[a].push_back(b);
    to[b].push_back(a);
    deg[a]++;
    deg[b]++;
  }
  //奇数次数の頂点数を求める
  int n_odd_deg = 0;
  rep(i, n) if (deg[i] & 1 == 1) n_odd_deg++;

  //木DPの為に枝を縮める
  dfs(0, -1);

  //二分探索でBを決める
  int l = -1, r = n;
  while (l + 1 < r) {
    int m = (l + r) / 2;
    //cout << l << " " << m << " " << r << endl;
    if (check(m))
      r = m;
    else
      l = m;
  }

  cout << n_odd_deg / 2 << " " << r << endl;
  return 0;
}