#include <bits/stdc++.h>
namespace {
using namespace std;
template <typename T>
inline bool whitespace(const vector<T> &) {
  return false;
}
template <typename T>
inline bool whitespace(const T &) {
  return true;
}
inline bool whitespace(const char) { return false; }
template <typename F, typename S>
inline bool whitespace(const pair<F, S> &) {
  return false;
}
template <typename F, typename S>
ostream &operator<<(ostream &os, const pair<F, S> &p) {
  os << p.first << (whitespace(p.second) ? " " : "") << p.second << "\n";
  return os;
}
template <typename F, typename S>
istream &operator>>(istream &is, pair<F, S> &p) {
  is >> p.first >> p.second;
  return is;
}
template <typename T>
istream &operator>>(istream &is, vector<T> &v) {
  for (T &t : v) is >> t;
  return is;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v) {
  for (const T &t : v) {
    os << t << (whitespace(t) ? " " : "");
  }
  os << "\n";
  return os;
}
template <typename T>
istream &operator>>(istream &is, deque<T> &v) {
  for (T &t : v) is >> t;
  return is;
}
template <typename T>
ostream &operator<<(ostream &os, const deque<T> &v) {
  for (const T &t : v) {
    os << t << (whitespace(t) ? " " : "");
  }
  os << "\n";
  return os;
}
template <typename T>
T gcd(T a, T b) {
  while (b) {
    T mod = a % b;
    a = b;
    b = mod;
  }
  return a;
}
template <typename T>
vector<T> prefix_sum(const vector<T> &v, long long from = 0) {
  vector<T> res(v.size() + 1 - from);
  res[0] = 0;
  for (long long i = from; i < v.size(); ++i)
    res[i + 1 - from] = res[i - from] + v[i];
  return res;
}
template <typename F, typename S>
F min(F a, S b) {
  return a < (F)b ? a : b;
}
template <typename F, typename S>
F max(F a, S b) {
  return a < (F)b ? b : a;
}
class exit_exception : exception {};
istream &in = cin;
ostream &out = cout;
template <typename T>
void answer(T ans) {
  out << ans << "\n";
  throw exit_exception();
}
struct autoint {
  long long x;
  autoint() { in >> x; }
  operator long long() { return x; }
  autoint(autoint &i) { x = i.x; }
  long long operator=(long long i) { return x = i; }
  long long operator--() { return --x; }
  long long operator--(signed) { return x--; }
  long long operator++() { return ++x; }
  long long operator++(signed) { return x++; }
};
}  // namespace
void solve();
signed main() {
  cin.tie(nullptr);
  cout.tie(nullptr);
  ios::sync_with_stdio(false);
  long long t = 1;
  do {
    try {
      solve();
    } catch (exit_exception &) {
    }
  } while (--t);
  return 0;
}
struct vertex {
  vertex *parent;
  vector<vertex *> children;
  long long n;
  bool leaf, has_leaves;
  bool has_even, has_odd;
  long long mx, mn;
  vertex(long long n, vertex *p, const vector<vector<long long>> &g)
      : n(n), has_leaves(false), mx(0), mn(0), has_even(false), has_odd(false) {
    parent = p;
    leaf = g[n].size() == 1;
    has_even = leaf;
    for (long long c : g[n]) {
      if (p && c == p->n) continue;
      children.push_back(new vertex(c, this, g));
      has_leaves |= children.back()->leaf;
      has_even |= children.back()->has_odd;
      has_odd |= children.back()->has_even;
    }
  }
};
long long dfs(vertex *cur, long long &mn) {
  if (cur->has_even && cur->has_odd) mn = 3;
  if (cur->leaf) return 0;
  long long ans =
      cur->has_leaves + count_if(cur->children.begin(), cur->children.end(),
                                 [](vertex *u) { return !u->leaf; });
  for (vertex *v : cur->children) ans += dfs(v, mn);
  return ans;
}
void solve() {
  autoint n;
  vector<vector<long long>> g(n);
  for (long long i = 0; i < n - 1; ++i) {
    autoint a, b;
    --a, --b;
    g[a].push_back(b);
    g[b].push_back(a);
  }
  vertex *root = new vertex(
      find_if(g.begin(), g.end(),
              [](const vector<long long> &h) { return h.size() > 1; }) -
          g.begin(),
      nullptr, g);
  long long mn = 1;
  long long mx = dfs(root, mn);
  cout << mn << ' ' << mx << '\n';
}

### Prompt

Develop a solution in CPP to the problem described below:

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>

### Response

```cpp
#include <bits/stdc++.h>
namespace {
using namespace std;
template <typename T>
inline bool whitespace(const vector<T> &) {
  return false;
}
template <typename T>
inline bool whitespace(const T &) {
  return true;
}
inline bool whitespace(const char) { return false; }
template <typename F, typename S>
inline bool whitespace(const pair<F, S> &) {
  return false;
}
template <typename F, typename S>
ostream &operator<<(ostream &os, const pair<F, S> &p) {
  os << p.first << (whitespace(p.second) ? " " : "") << p.second << "\n";
  return os;
}
template <typename F, typename S>
istream &operator>>(istream &is, pair<F, S> &p) {
  is >> p.first >> p.second;
  return is;
}
template <typename T>
istream &operator>>(istream &is, vector<T> &v) {
  for (T &t : v) is >> t;
  return is;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v) {
  for (const T &t : v) {
    os << t << (whitespace(t) ? " " : "");
  }
  os << "\n";
  return os;
}
template <typename T>
istream &operator>>(istream &is, deque<T> &v) {
  for (T &t : v) is >> t;
  return is;
}
template <typename T>
ostream &operator<<(ostream &os, const deque<T> &v) {
  for (const T &t : v) {
    os << t << (whitespace(t) ? " " : "");
  }
  os << "\n";
  return os;
}
template <typename T>
T gcd(T a, T b) {
  while (b) {
    T mod = a % b;
    a = b;
    b = mod;
  }
  return a;
}
template <typename T>
vector<T> prefix_sum(const vector<T> &v, long long from = 0) {
  vector<T> res(v.size() + 1 - from);
  res[0] = 0;
  for (long long i = from; i < v.size(); ++i)
    res[i + 1 - from] = res[i - from] + v[i];
  return res;
}
template <typename F, typename S>
F min(F a, S b) {
  return a < (F)b ? a : b;
}
template <typename F, typename S>
F max(F a, S b) {
  return a < (F)b ? b : a;
}
class exit_exception : exception {};
istream &in = cin;
ostream &out = cout;
template <typename T>
void answer(T ans) {
  out << ans << "\n";
  throw exit_exception();
}
struct autoint {
  long long x;
  autoint() { in >> x; }
  operator long long() { return x; }
  autoint(autoint &i) { x = i.x; }
  long long operator=(long long i) { return x = i; }
  long long operator--() { return --x; }
  long long operator--(signed) { return x--; }
  long long operator++() { return ++x; }
  long long operator++(signed) { return x++; }
};
}  // namespace
void solve();
signed main() {
  cin.tie(nullptr);
  cout.tie(nullptr);
  ios::sync_with_stdio(false);
  long long t = 1;
  do {
    try {
      solve();
    } catch (exit_exception &) {
    }
  } while (--t);
  return 0;
}
struct vertex {
  vertex *parent;
  vector<vertex *> children;
  long long n;
  bool leaf, has_leaves;
  bool has_even, has_odd;
  long long mx, mn;
  vertex(long long n, vertex *p, const vector<vector<long long>> &g)
      : n(n), has_leaves(false), mx(0), mn(0), has_even(false), has_odd(false) {
    parent = p;
    leaf = g[n].size() == 1;
    has_even = leaf;
    for (long long c : g[n]) {
      if (p && c == p->n) continue;
      children.push_back(new vertex(c, this, g));
      has_leaves |= children.back()->leaf;
      has_even |= children.back()->has_odd;
      has_odd |= children.back()->has_even;
    }
  }
};
long long dfs(vertex *cur, long long &mn) {
  if (cur->has_even && cur->has_odd) mn = 3;
  if (cur->leaf) return 0;
  long long ans =
      cur->has_leaves + count_if(cur->children.begin(), cur->children.end(),
                                 [](vertex *u) { return !u->leaf; });
  for (vertex *v : cur->children) ans += dfs(v, mn);
  return ans;
}
void solve() {
  autoint n;
  vector<vector<long long>> g(n);
  for (long long i = 0; i < n - 1; ++i) {
    autoint a, b;
    --a, --b;
    g[a].push_back(b);
    g[b].push_back(a);
  }
  vertex *root = new vertex(
      find_if(g.begin(), g.end(),
              [](const vector<long long> &h) { return h.size() > 1; }) -
          g.begin(),
      nullptr, g);
  long long mn = 1;
  long long mx = dfs(root, mn);
  cout << mn << ' ' << mx << '\n';
}

```