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 <iostream>
#include <vector>
#include <algorithm>
#include <cassert>

using namespace std;

const int MAX_N = 1e5 + 5;
const int MAX_LG = 17;

vector<int> adj [MAX_N];

int max_fold_without (const vector<int> &v, int idx) {
  int lptr = 0;
  if (lptr == idx) lptr++;
  int rptr = (int) v.size() - 1;
  if (rptr == idx) rptr--;

  int mx = 0;
  while (lptr < rptr) {
    mx = max(mx, v[lptr] + v[rptr]);

    lptr++;
    if (lptr == idx) lptr++;
    rptr--;
    if (rptr == idx) rptr--;
  }

  return mx;
}

int dp [MAX_N]; // cheapest thing we can send up
int cap;
bool error;
void dfs (int u, int p) {
  for (int nxt : adj[u]) {
    if (nxt != p) {
      dfs(nxt, u);
    }
  }

  vector<int> ups;
  for (int nxt : adj[u]) {
    if (nxt != p) {
      ups.push_back(dp[nxt]);
    }
  }

  if ((int) adj[u].size() % 2 == 1) {
    ups.push_back(0);
  }
  sort(ups.begin(), ups.end());

  if (u == p) {
    int fold = max_fold_without(ups, -1);
    if (fold > cap) error = 1;
    return;
  }

  if (max_fold_without(ups, (int) ups.size() - 1) > cap) {
    error = 1;
  } else if (max_fold_without(ups, 0) <= cap) {
    dp[u] = ups[0];
  } else {
    int ans = 0;
    for (int k = 1 << MAX_LG; k != 0; k /= 2) {
      if (ans + k < (int) ups.size() && max_fold_without(ups, ans + k) > cap) {
        ans += k;
      }
    }
    dp[u] = ups[ans + 1];
  }
  dp[u]++;

  if (dp[u] > cap) error = 1;
}

bool try_with (int _cap) {
  cap = _cap;
  error = 0;
  dfs(1, 1);
  return error;
}

int main () {
  ios::sync_with_stdio(false);

  int n;
  cin >> n;

  for (int i = 0; i < n - 1; i++) {
    int u, v;
    cin >> u >> v;

    adj[u].push_back(v);
    adj[v].push_back(u);
  }

  int oddc = 0;
  for (int i = 1; i <= n; i++) {
    if ((int) adj[i].size() % 2 == 1) oddc++;
  }
  
  int ans = 0;
  for (int k = 1 << MAX_LG; k != 0; k /= 2) {
    cap = ans + k;
    error = 0;
    dfs(1, 1);
    if (error) {
      ans += k;
    }
  }

  cout << oddc / 2 << " " << ans + 1 << endl;
}