output_description: Print `Alice` if Alice wins; print `Bob` if Bob wins.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N
      x_1 y_1
      x_2 y_2
      :
      x_{N-1} y_{N-1}
attempt: def main():
      n = int(input())
      ab = [list(map(int, input().split())) for _ in [0] * (n - 1)]
      g = [[] for _ in [0] * n]
      [g[a - 1].append(b - 1) for a, b in ab]
      [g[b - 1].append(a - 1) for a, b in ab]
      root = 0  # 根
      d = [-1] * n  # 根からの距離
      d[root] = 0
      q = [root]
      cnt = 0
      while q:  # BFS
          cnt += 1
          qq = []
          while q:
              i = q.pop()
              for j in g[i]:
                  if d[j] == -1:
                      d[j] = cnt
                      qq.append(j)
          q = qq
      grundy = [0] * n
  
      dd = [j for i, j in sorted([(j, i) for i, j in enumerate(d)])[::-1]]
  
      for i in dd:
          dist = d[i]
          xorlist = []
          xor = 0
          for j in g[i]:
              if d[j] > dist:
                  xorlist.append(grundy[j] + 1)
          for j in xorlist:
              xor ^= j
          grundy[i] = xor
  
      if grundy[0]:
          print("Alice")
      else:
          print("Bob")
  
  
  main()
  
problem_description: Statement
  
  There is a tree with N vertices numbered 1, 2, ..., N. The edges of the tree
  are denoted by (x_i, y_i).
  
  On this tree, Alice and Bob play a game against each other. Starting from
  Alice, they alternately perform the following operation:
  
    * Select an existing edge and remove it from the tree, disconnecting it into two separate connected components. Then, remove the component that does not contain Vertex 1.
  
  A player loses the game when he/she is unable to perform the operation.
  Determine the winner of the game assuming that both players play optimally.
samples: [{"input": "5\n    1 2\n    2 3\n    2 4\n    4 5", "output": "Alice\n    \n\nIf Alice first removes the edge connecting Vertices 1 and 2, the tree becomes\na single vertex tree containing only Vertex 1. Since there is no edge anymore,\nBob cannot perform the operation and Alice wins.\n\n* * *"}, {"input": "5\n    1 2\n    2 3\n    1 4\n    4 5", "output": "Bob\n    \n\n* * *"}, {"input": "6\n    1 2\n    2 4\n    5 1\n    6 3\n    3 2", "output": "Alice\n    \n\n* * *"}, {"input": "7\n    1 2\n    3 7\n    4 6\n    2 3\n    2 4\n    1 5", "output": "Bob"}]