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)
  
  def dfs(v,pv,n):
      #print(v,pv,len(edge[v]))
      if v!=0:
          if len(edge[v])==1:
              return 1
          temp=[]
          for nv in edge[v]:
              if nv!=pv:
                  r=dfs(nv,v,n)
                  if r==-1:
                      return -1
                  temp.append(r)
          if len(temp)%2==0:
              temp.append(0)
          elif len(temp)==1:
              return temp[0]+1
          temp.sort()
          que=[]
          #ban=set([])
          k=len(temp)//2
          for i in range(k):
              heapq.heappush(que,(-temp[i+1]-temp[-i-1],i+1,N-1-i))
          for i in range(k):
              val,id1,id2=heapq.heappop(que)
              while id1+id2==N and id1=<i:
                  val,id1,id2=heapq.heappop(que)
              if val>=-n:
                  return temp[i]+1
              heapq.heappush(que,(-temp[i]-temp[-i-1],i,N-1-i))
              #ban.add((i+1,N-1-i))
          for i in range(k):
              val,id1,id2=heapq.heappop(que)
              while (id1+id2==N) or (id1+id2==N-1 and id2<i+k):
                  val,id1,id2=heapq.heappop(que)
              if val>=-n:
                  return temp[i+k]+1
              heapq.heappush(que,(-temp[k-1-i]-temp[i+k],k-1-i,i+k))
              #ban.add((N-1-i-k,i+k))
          val,id1,id2=heapq.heappop(que)
          while id1+id2!=2*k-1:
              val,id1,id2=heapq.heappop(que)
          if val>=-n:
              return temp[-1]+1
  
          return -1
      else:
          temp=[]
          for nv in edge[v]:
              if nv!=pv:
                  r=dfs(nv,v,n)
                  if r==-1:
                      return False
                  temp.append(r)
          if len(temp)%2==1:
              temp.append(0)
          temp.sort()
          k=len(temp)//2
          for i in range(k):
              test=temp[i]+temp[-i-1]
              if test>n:
                  return False
          return True
  
  A=(len(edge[0])+1)//2
  for i in range(1,N):
      A+=(len(edge[i])-1)//2
  
  start=0
  end=N-1
  while end-start>1:
      t=(end+start)//2
      if dfs(0,-1,t):
          end=t
      else:
          start=t
  
  print(A,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"}]