N, u, v = list(map(int, input().split()))
class ver:
  def __init__(self, x):
    self.__x = x
    self.__p = -1
    self.__c = []
    self.__d = -1
    
  def get_p(self):
    return self.__p
  
  def set_p(self, x):
    self.__p = x
    
  def get_c(self):
    return self.__c
  
  def add_c(self, x):
    self.__c.append(x)
  
  def pop_c(self, x):
    return self.__c.pop(self.__c.index(x))
  
  def set_d(self, d):
    self.__d = d
    
  def get_d(self):
    return self.__d
    
class tree:
  def __init__(self, N, v):
    self.__N = N
    self.__a = [ver(i) for i in range(N+1)]
    self.__root = v
    
  def find_root(self, x):
    if self.__a[x].get_p() == -1:
      return x
    else:
      return self.__find(self.__a[x].get_p())
    
  def leaves(self):
    res = []
    for i, var in enumerate(self.__a):
      if not var.get_c():
        res.append(i)
    return res
  
  def add_(self, x, y):
    self.__a[x].add_c(y)
    self.__a[y].add_c(x)
  
  def change_root(self, v, d):
    self.__a[v].set_d(d)
    d += 1
    for i in self.__a[v].get_c():
      self.__a[i].set_p(self.__a[i].pop_c(v)) 
      self.change_root(i, d)
      
  def show_p(self):
    res = []
    for i in self.__a:
      res.append(i.get_p())
    return res
  
  def show_d(self):
    res = []
    for i in self.__a:
      res.append(i.get_d())
    return res
  
t = tree(N, v)
for _ in range(N-1):
  x, y = map(int, input().split())
  t.add_(x, y)
t.change_root(v, 0)
print(t.show_p())
print(t.show_d())
