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 <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cmath>
#include <iomanip>
#include <cassert>
#include <bitset>
using namespace std;

typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end())
#define index(xs, x) (int)(lower_bound(all(xs), x) - xs.begin())
#define _1 first
#define _2 second
#define pb push_back
#define INF 1145141919
#define MOD 1000000007

int N, X;
vector<int> G[100000];
int dp[100000];
P rooted[100000];

int solve(vector<int> &A, int except) {
  int r = A.size()-1, c = 0;
  rep(l, A.size()) if (l != except) {
    while (l < r && (r == except || A[l]+A[r] > X)) r--;
    if (l >= r) break;
    c++, r--;
  }
  //cout<<"solve({";rep(i, A.size()) if (i!=except)cout<<A[i]<<",";cout<<"}, X="<<X<<") = "<<c<<"\n";
  return c;
}

void dfs(int x, int p) {
  for (int t : G[x]) if (t != p) dfs(t, x);
  int sum = 0;
  vector<int> ds;
  for (int t : G[x]) if (t != p) sum += rooted[t]._1, ds.pb(rooted[t]._2);
  sort(all(ds));
  int m = solve(ds, -1);
  dp[x] = sum-m;
  rooted[x] = P(dp[x]+1, 1);
  if (ds.size() == 0) return;

  int r = ds.size()-1;
  while (r >= 0 && ds[r]+1 > X) r--;
  if (r < 0) return;
  int best = solve(ds, r);
  int lo = -1, hi = r;
  while (hi - lo > 1) {
    int mid = (lo + hi) / 2;
    if (solve(ds, mid) == best) hi = mid;
    else lo = mid;
  }
  rooted[x] = min(rooted[x], P(sum-best, ds[hi]+1));
}

signed main() {
  ios::sync_with_stdio(false); cin.tie(0);
  cin >> N;
  rep(i, N-1) {
    int a, b;
    cin >> a >> b;
    a--, b--;
    G[a].pb(b);
    G[b].pb(a);
  }
  X = N;
  dfs(0, -1);
  int best = dp[0];
  int lo = 0, hi = N;
  while (hi - lo > 1) {
    int mid = (lo + hi) / 2;
    X = mid;
    dfs(0, -1);
    if (dp[0] == best) hi = mid;
    else lo = mid;
  }
  cout << best << " " << hi << "\n";
  //for (X=1; X<=N; X++) { dfs(0, -1);cout<<"X="<<X<<": "<<dp[0]<<"\n"; }
  return 0;
}