#include <bits/stdc++.h>
template <typename T, int M, int N>
struct tuple_getter {
  static void get(std::istream &is, T &x) {
    is >> std::get<M>(x);
    tuple_getter<T, M + 1, N>::get(is, x);
  }
};
template <typename T, int N>
struct tuple_getter<T, N, N> {
  static void get(std::istream &is, T &x) { is >> std::get<N>(x); }
};
template <typename... Args>
std::istream &operator>>(std::istream &is, std::tuple<Args...> &t) {
  tuple_getter<std::tuple<Args...>, 0, sizeof...(Args) - 1>::get(is, t);
  return is;
}
template <typename T, typename U>
std::istream &operator>>(std::istream &is, std::pair<T, U> &p) {
  is >> p.first >> p.second;
  return is;
}
template <typename T>
std::istream &operator>>(std::istream &is, std::vector<T> &v) {
  for (T &x : v) is >> x;
  return is;
}
namespace sub {
template <typename T>
constexpr typename std::enable_if<std::is_integral<T>::value, T>::type
inf_sub() {
  return std::numeric_limits<T>::max() / 2 - 1000;
}
template <typename T>
constexpr typename std::enable_if<std::is_floating_point<T>::value, T>::type
inf_sub() {
  return std::min(std::numeric_limits<T>::max() / 2 - 1000, T(1e50));
}
}  // namespace sub
template <typename T>
constexpr T inf() {
  static_assert(std::is_arithmetic<T>::value, "T must be arithmetic value");
  return sub::inf_sub<T>();
}
template <typename T>
constexpr T zero() {
  static_assert(std::is_arithmetic<T>::value, "T must be arithmetic value");
  return T(0);
}
const long double pi = acos(-1.0);
template <typename T, int M, int N>
struct tuple_printer {
  static void print(std::ostream &os, const T &x) {
    os << std::get<M>(x) << " ";
    tuple_printer<T, M + 1, N>::print(os, x);
  }
};
template <typename T, int N>
struct tuple_printer<T, N, N> {
  static void print(std::ostream &os, const T &x) { os << std::get<N>(x); }
};
template <typename... Args>
std::ostream &operator<<(std::ostream &os, const std::tuple<Args...> &t) {
  tuple_printer<std::tuple<Args...>, 0, sizeof...(Args) - 1>::print(os, t);
  return os;
}
template <typename T, typename U>
std::ostream &operator<<(std::ostream &os, const std::pair<T, U> &p) {
  os << p.first << " " << p.second;
  return os;
}
template <typename T>
std::ostream &operator<<(std::ostream &os, const std::vector<T> &v) {
  for (auto it = v.begin(); it != v.end(); ++it) {
    if (it != v.begin()) os << " ";
    os << *it;
  }
  return os;
}
template <typename T>
std::ostream &operator<<(std::ostream &os, const std::set<T> &v) {
  for (auto it = v.begin(); it != v.end(); ++it) {
    if (it != v.begin()) os << " ";
    os << *it;
  }
  return os;
}
template <typename T>
T &chmin(T &a, const T &b) {
  return a = std::min(a, b);
}
template <typename T>
T &chmax(T &a, const T &b) {
  return a = std::max(a, b);
}
class range {
  class index_type {
    int x;

   public:
    index_type(int x_) : x(x_) {}
    int operator*() const { return x; }
    bool operator!=(index_type &r) { return x < r.x; }
    void operator++() { ++x; }
  };
  index_type i, n;

 public:
  range(int n_) : i(0), n(n_) {}
  range(int i_, int n_) : i(i_), n(n_) {}
  index_type &begin() { return i; }
  index_type &end() { return n; }
};
using ll = long long;
using ld = long double;
using namespace std;
struct yes_no : std::numpunct<char> {
  string_type do_truename() const { return "Yes"; }
  string_type do_falsename() const { return "No"; }
};
struct Initialize {
  Initialize() {
    std::locale loc(std::locale(), new yes_no);
    std::cout << std::boolalpha << std::setprecision(11) << std::fixed;
    std::cout.imbue(loc);
  }
};
const Initialize initialize;
template <class edge_t>
class graph_t {
  std::vector<std::vector<edge_t>> g;

 public:
  using reference = std::vector<edge_t> &;
  using const_reference = const std::vector<edge_t> &;
  using iterator = typename std::vector<edge_t>::iterator;
  graph_t() : g(0) { ; }
  graph_t(int n) : g(n) { ; }
  int size() const { return g.size(); }
  void push_back(const std::vector<edge_t> &es) { g.push_back(es); }
  reference operator[](int x) { return g[x]; }
  const_reference operator[](int x) const { return g[x]; }
  iterator &begin() { return begin(g); }
  iterator &end() { return end(g); }
};
class BidirectedEdge {
 public:
  using cost_type = int;
  int from, to;
  static const cost_type cost = 1;
  BidirectedEdge(int s, int t) : from(s), to(t) { ; }
};
using BidirectedGraph = graph_t<BidirectedEdge>;
void add_edge(BidirectedGraph &g, int from, int to) {
  g[from].emplace_back(from, to);
  g[to].emplace_back(to, from);
}
template <typename edge_t, typename cost_type = typename edge_t::cost_type>
std::vector<cost_type> bfs01(const graph_t<edge_t> &g, int s) {
  static_assert(std::is_integral<cost_type>::value, "cost must be integer");
  std::vector<cost_type> d(g.size(), inf<cost_type>());
  d[s] = cost_type(0);
  std::deque<std::pair<cost_type, int>> que;
  que.emplace_back(zero<cost_type>(), s);
  while (!que.empty()) {
    auto top = que.front();
    que.pop_front();
    cost_type dist = top.first;
    int v = top.second;
    if (d[v] < dist) continue;
    for (const auto &e : g[v]) {
      if (d[e.to] > d[v] + e.cost) {
        d[e.to] = d[v] + e.cost;
        if (e.cost == cost_type(1)) {
          que.emplace_back(d[e.to], e.to);
        } else if (e.cost == cost_type(0)) {
          que.emplace_front(d[e.to], e.to);
        } else {
          assert(false);
        }
      }
    }
  }
  return d;
}
class UnionFind {
  std::vector<int> p;

 public:
  UnionFind(int n) : p(n, -1) {}
  int root(int x) { return p[x] < 0 ? x : p[x] = root(p[x]); }
  bool same(int x, int y) { return root(x) == root(y); }
  bool unite(int x, int y) {
    x = root(x);
    y = root(y);
    if (x == y) return false;
    if (p[y] < p[x]) std::swap(x, y);
    if (p[x] == p[y]) --p[x];
    p[y] = x;
    return true;
  }
};
using Graph = BidirectedGraph;
int main() {
  int N;
  scanf("%d", &N);
  Graph g(N);
  for (int i = 0; i < (int)(N - 1); i++) {
    int u, v;
    scanf("%d%d", &u, &v);
    --u;
    --v;
    add_edge(g, u, v);
  }
  auto d = bfs01(g, 0);
  bool even = false, odd = false;
  for (int i = 0; i < (int)(N); i++) {
    if (int(g[i].size()) == 1) {
      if (d[i] % 2 == 0)
        even = true;
      else
        odd = true;
    }
  }
  int min = (even && odd) ? 3 : 1;
  UnionFind uf(N);
  int size = N - 1;
  for (int i = 0; i < (int)(N); i++) {
    int orig = -1;
    for (auto e : g[i]) {
      if (int(g[e.to].size()) == 1) {
        if (orig == -1)
          orig = e.to;
        else
          size -= uf.unite(orig, e.to);
      }
    }
  }
  cout << min << " " << size << endl;
  return 0;
}

### Prompt

In cpp, your task is to solve the following problem:

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>
template <typename T, int M, int N>
struct tuple_getter {
  static void get(std::istream &is, T &x) {
    is >> std::get<M>(x);
    tuple_getter<T, M + 1, N>::get(is, x);
  }
};
template <typename T, int N>
struct tuple_getter<T, N, N> {
  static void get(std::istream &is, T &x) { is >> std::get<N>(x); }
};
template <typename... Args>
std::istream &operator>>(std::istream &is, std::tuple<Args...> &t) {
  tuple_getter<std::tuple<Args...>, 0, sizeof...(Args) - 1>::get(is, t);
  return is;
}
template <typename T, typename U>
std::istream &operator>>(std::istream &is, std::pair<T, U> &p) {
  is >> p.first >> p.second;
  return is;
}
template <typename T>
std::istream &operator>>(std::istream &is, std::vector<T> &v) {
  for (T &x : v) is >> x;
  return is;
}
namespace sub {
template <typename T>
constexpr typename std::enable_if<std::is_integral<T>::value, T>::type
inf_sub() {
  return std::numeric_limits<T>::max() / 2 - 1000;
}
template <typename T>
constexpr typename std::enable_if<std::is_floating_point<T>::value, T>::type
inf_sub() {
  return std::min(std::numeric_limits<T>::max() / 2 - 1000, T(1e50));
}
}  // namespace sub
template <typename T>
constexpr T inf() {
  static_assert(std::is_arithmetic<T>::value, "T must be arithmetic value");
  return sub::inf_sub<T>();
}
template <typename T>
constexpr T zero() {
  static_assert(std::is_arithmetic<T>::value, "T must be arithmetic value");
  return T(0);
}
const long double pi = acos(-1.0);
template <typename T, int M, int N>
struct tuple_printer {
  static void print(std::ostream &os, const T &x) {
    os << std::get<M>(x) << " ";
    tuple_printer<T, M + 1, N>::print(os, x);
  }
};
template <typename T, int N>
struct tuple_printer<T, N, N> {
  static void print(std::ostream &os, const T &x) { os << std::get<N>(x); }
};
template <typename... Args>
std::ostream &operator<<(std::ostream &os, const std::tuple<Args...> &t) {
  tuple_printer<std::tuple<Args...>, 0, sizeof...(Args) - 1>::print(os, t);
  return os;
}
template <typename T, typename U>
std::ostream &operator<<(std::ostream &os, const std::pair<T, U> &p) {
  os << p.first << " " << p.second;
  return os;
}
template <typename T>
std::ostream &operator<<(std::ostream &os, const std::vector<T> &v) {
  for (auto it = v.begin(); it != v.end(); ++it) {
    if (it != v.begin()) os << " ";
    os << *it;
  }
  return os;
}
template <typename T>
std::ostream &operator<<(std::ostream &os, const std::set<T> &v) {
  for (auto it = v.begin(); it != v.end(); ++it) {
    if (it != v.begin()) os << " ";
    os << *it;
  }
  return os;
}
template <typename T>
T &chmin(T &a, const T &b) {
  return a = std::min(a, b);
}
template <typename T>
T &chmax(T &a, const T &b) {
  return a = std::max(a, b);
}
class range {
  class index_type {
    int x;

   public:
    index_type(int x_) : x(x_) {}
    int operator*() const { return x; }
    bool operator!=(index_type &r) { return x < r.x; }
    void operator++() { ++x; }
  };
  index_type i, n;

 public:
  range(int n_) : i(0), n(n_) {}
  range(int i_, int n_) : i(i_), n(n_) {}
  index_type &begin() { return i; }
  index_type &end() { return n; }
};
using ll = long long;
using ld = long double;
using namespace std;
struct yes_no : std::numpunct<char> {
  string_type do_truename() const { return "Yes"; }
  string_type do_falsename() const { return "No"; }
};
struct Initialize {
  Initialize() {
    std::locale loc(std::locale(), new yes_no);
    std::cout << std::boolalpha << std::setprecision(11) << std::fixed;
    std::cout.imbue(loc);
  }
};
const Initialize initialize;
template <class edge_t>
class graph_t {
  std::vector<std::vector<edge_t>> g;

 public:
  using reference = std::vector<edge_t> &;
  using const_reference = const std::vector<edge_t> &;
  using iterator = typename std::vector<edge_t>::iterator;
  graph_t() : g(0) { ; }
  graph_t(int n) : g(n) { ; }
  int size() const { return g.size(); }
  void push_back(const std::vector<edge_t> &es) { g.push_back(es); }
  reference operator[](int x) { return g[x]; }
  const_reference operator[](int x) const { return g[x]; }
  iterator &begin() { return begin(g); }
  iterator &end() { return end(g); }
};
class BidirectedEdge {
 public:
  using cost_type = int;
  int from, to;
  static const cost_type cost = 1;
  BidirectedEdge(int s, int t) : from(s), to(t) { ; }
};
using BidirectedGraph = graph_t<BidirectedEdge>;
void add_edge(BidirectedGraph &g, int from, int to) {
  g[from].emplace_back(from, to);
  g[to].emplace_back(to, from);
}
template <typename edge_t, typename cost_type = typename edge_t::cost_type>
std::vector<cost_type> bfs01(const graph_t<edge_t> &g, int s) {
  static_assert(std::is_integral<cost_type>::value, "cost must be integer");
  std::vector<cost_type> d(g.size(), inf<cost_type>());
  d[s] = cost_type(0);
  std::deque<std::pair<cost_type, int>> que;
  que.emplace_back(zero<cost_type>(), s);
  while (!que.empty()) {
    auto top = que.front();
    que.pop_front();
    cost_type dist = top.first;
    int v = top.second;
    if (d[v] < dist) continue;
    for (const auto &e : g[v]) {
      if (d[e.to] > d[v] + e.cost) {
        d[e.to] = d[v] + e.cost;
        if (e.cost == cost_type(1)) {
          que.emplace_back(d[e.to], e.to);
        } else if (e.cost == cost_type(0)) {
          que.emplace_front(d[e.to], e.to);
        } else {
          assert(false);
        }
      }
    }
  }
  return d;
}
class UnionFind {
  std::vector<int> p;

 public:
  UnionFind(int n) : p(n, -1) {}
  int root(int x) { return p[x] < 0 ? x : p[x] = root(p[x]); }
  bool same(int x, int y) { return root(x) == root(y); }
  bool unite(int x, int y) {
    x = root(x);
    y = root(y);
    if (x == y) return false;
    if (p[y] < p[x]) std::swap(x, y);
    if (p[x] == p[y]) --p[x];
    p[y] = x;
    return true;
  }
};
using Graph = BidirectedGraph;
int main() {
  int N;
  scanf("%d", &N);
  Graph g(N);
  for (int i = 0; i < (int)(N - 1); i++) {
    int u, v;
    scanf("%d%d", &u, &v);
    --u;
    --v;
    add_edge(g, u, v);
  }
  auto d = bfs01(g, 0);
  bool even = false, odd = false;
  for (int i = 0; i < (int)(N); i++) {
    if (int(g[i].size()) == 1) {
      if (d[i] % 2 == 0)
        even = true;
      else
        odd = true;
    }
  }
  int min = (even && odd) ? 3 : 1;
  UnionFind uf(N);
  int size = N - 1;
  for (int i = 0; i < (int)(N); i++) {
    int orig = -1;
    for (auto e : g[i]) {
      if (int(g[e.to].size()) == 1) {
        if (orig == -1)
          orig = e.to;
        else
          size -= uf.unite(orig, e.to);
      }
    }
  }
  cout << min << " " << size << endl;
  return 0;
}

```