output_description: If there is no permutation that can generate a tree isomorphic to Takahashi's
  favorite tree, print `-1`. If it exists, print the lexicographically smallest
  such permutation, with spaces in between.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      n
      v_1 w_1
      v_2 w_2
      :
      v_{n-1} w_{n-1}
attempt: #!/usr/bin/env python3
  
  
  def solve(n, adj_list, d):
  
      s = []
      path_adj_list = [[] for _ in range(n)]
      for v in range(n):
          if 1 < d[v]:
              p = path_adj_list[v]
              for w in adj_list[v]:
                  if 1 < d[w]:
                      p.append(w)
              if 2 < len(p):
                  print(-1)
                  return
              if len(p) == 1:
                  s.append(v)
  
      if len(s) == 0:
          ans = [1] + [v for v in range(3, n + 1)] + [2]
          print(" ".join(list(map(str, ans))))
          return
  
      visited = [False] * n
      v, w = s
      while v != w and d[v] == d[w]:
          visited[v] = True
          visited[w] = True
          f = False
          for nv in path_adj_list[v]:
              if not visited[nv]:
                  f = True
                  v = nv
                  break
          if not f:
              break
          f = False
          for nw in path_adj_list[w]:
              if not visited[nw]:
                  f = True
                  w = nw
                  break
          if not f:
              break
  
      if d[v] > d[w]:
          v = s[1]
      else:
          v = s[0]
  
      visited = [False] * n
      visited[v] = True
      ans = [1] + [w for w in range(3, d[v] + 1)] + [2]
      c = d[v]
      v = path_adj_list[v][0]
      while True:
          visited[v] = True
          ans += [w for w in range(c + 2, c + d[v])] + [c + 1]
          c += d[v] - 1
          f = False
          for nv in path_adj_list[v]:
              if not visited[nv]:
                  f = True
                  v = nv
                  break
          if not f:
              break
  
      ans += [n]
  
      print(" ".join(list(map(str, ans))))
      return
  
  
  def main():
      n = input()
      n = int(n)
      adj_list = [[] for _ in range(n)]
      d = [0] * n
      for _ in range(n - 1):
          v, w = input().split()
          v = int(v) - 1
          w = int(w) - 1
          adj_list[v].append(w)
          adj_list[w].append(v)
          d[v] += 1
          d[w] += 1
  
      solve(n, adj_list, d)
  
  
  if __name__ == "__main__":
      main()
  
problem_description: Statement
  
  Takahashi has an ability to generate a tree using a permutation
  (p_1,p_2,...,p_n) of (1,2,...,n), in the following process:
  
  First, prepare Vertex 1, Vertex 2, ..., Vertex N. For each i=1,2,...,n,
  perform the following operation:
  
    * If p_i = 1, do nothing.
    * If p_i \neq 1, let j' be the largest j such that p_j < p_i. Span an edge between Vertex i and Vertex j'.
  
  Takahashi is trying to make his favorite tree with this ability. His favorite
  tree has n vertices from Vertex 1 through Vertex n, and its i-th edge connects
  Vertex v_i and w_i. Determine if he can make a tree isomorphic to his favorite
  tree by using a proper permutation. If he can do so, find the
  lexicographically smallest such permutation.
samples: [{"input": "6\n    1 2\n    1 3\n    1 4\n    1 5\n    5 6", "output": "1 2 4 5 3 6\n    \n\nIf the permutation (1, 2, 4, 5, 3, 6) is used to generate a tree, it looks as\nfollows:\n\n![](https://img.atcoder.jp/arc095/db000b879402aed649a1516620eb1e21.png)\n\nThis is isomorphic to the given graph.\n\n* * *"}, {"input": "6\n    1 2\n    2 3\n    3 4\n    1 5\n    5 6", "output": "1 2 3 4 5 6\n    \n\n* * *"}, {"input": "15\n    1 2\n    1 3\n    2 4\n    2 5\n    3 6\n    3 7\n    4 8\n    4 9\n    5 10\n    5 11\n    6 12\n    6 13\n    7 14\n    7 15", "output": "-1"}]