output_description: For the lexicographically smallest (A,B), print A and B with a space in
  between.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N
      a_1 b_1
      :
      a_{N-1} b_{N-1}
attempt: import sys, heapq
  
  input = sys.stdin.readline
  sys.setrecursionlimit(2 * 10**5)
  
  N = int(input())
  edge = [[] for i in range(N)]
  for _ in range(N - 1):
      a, b = map(int, input().split())
      edge[a - 1].append(b - 1)
      edge[b - 1].append(a - 1)
  
  temp = [[0 for j in range(len(edge[i]) - 1)] for i in range(N)]
  temp[0].append(0)
  for i in range(1, N):
      if len(temp[i]) % 2 == 0:
          temp[i].append(0)
  if len(temp[0]) % 2 == 1:
      temp[0].append(0)
  
  
  def clear():
      for i in range(N):
          temp[i].sort()
          for j in range(len(temp[i])):
              temp[i][j] = 0
  
  
  start = 0
  end = N - 1
  while end - start > 1:
      t = (end + start) // 2
      clear()
      end = t
  
  print(end)
  
problem_description: Statement
  
  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.
samples: [{"input": "7\n    1 2\n    2 3\n    2 4\n    4 5\n    4 6\n    6 7", "output": "3 2\n    \n\nWe can make a Christmas Tree as shown in the figure below:\n\n![](https://img.atcoder.jp/arc088/96f78221624d6a13628f6052f5db697d.png)\n\n* * *"}, {"input": "8\n    1 2\n    2 3\n    3 4\n    4 5\n    5 6\n    5 7\n    5 8", "output": "2 5\n    \n\n* * *"}, {"input": "10\n    1 2\n    2 3\n    3 4\n    2 5\n    6 5\n    6 7\n    7 8\n    5 9\n    10 5", "output": "3 4"}]