from queue import *

# строим граф из входных данных
def solve_graph(input_list):
    vertices_number = input_list[0][0]
    root_id = input_list[0][1]
    edges_number = vertices_number - 1

    vertices = []
    for i in range(0, vertices_number):
        vertices.append({ 'id': i, 'left': None, 'right': None })

    root_vertice = vertices[root_id]

    # создаём таблицу «ID вершины → список соседей»
    # для больших деревьев с ней где-то в ≈310 раз быстрее
    edges = {}
    for i in range(1, edges_number + 1):
        entry = input_list[i]

        if entry[0] in edges:
            edges[entry[0]].append(entry[1])
        else:
            edges[entry[0]] = [ entry[1] ]

        if entry[1] in edges:
            edges[entry[1]].append(entry[0])
        else:
            edges[entry[1]] = [ entry[0] ]

    arrange_children_wrapper = None

    # распихаем потомков по слотам
    def arrange_children(vertice, vertice_parent_id):
        vertice_id = vertice['id']

        # добавляем потомка в незанятый слот
        def add_child(child):
            if vertice['left'] == None:
                vertice['left'] = child
            else:
                vertice['right'] = child

        # быстренько выдёргиваем соседей из той таблицы
        if vertice_id in edges:
            for i in edges[vertice_id]:
                if i != vertice_parent_id:
                    add_child(vertices[i])

    # без рекурсии
    queue = Queue()

    current_vertice = root_vertice
    current_parent_id = -1

    while True:
        arrange_children(current_vertice, current_parent_id)

        left = current_vertice['left']
        right = current_vertice['right']
        current_parent_id = current_vertice['id']

        if left != None:
            current_vertice = left
            if right != None:
                queue.put(( right, current_parent_id ))
        elif right != None:
            current_vertice = right
        elif not queue.empty():
            current_vertice, current_parent_id = queue.get()
        else:
            break

    return root_vertice

# размер графа (пусть и пострашнее, зато теперь без рекурсии)
def calculate_width(vertice):
    if vertice == None: return 0

    queue = Queue()
    current_vertice = vertice

    width = 0

    while True:
        width = width + 1

        left = current_vertice['left']
        right = current_vertice['right']

        if left != None:
            current_vertice = left
            if right != None:
                queue.put(right)
        elif right != None:
            current_vertice = right
        elif not queue.empty():
            current_vertice = queue.get()
        else:
            return width

def calculate_height(vertice):
    if vertice == None: return 0

    queue = Queue()
    current_vertice = vertice
    current_height = 0

    height = 0

    while True:
        current_height = current_height + 1
        height = max(height, current_height)

        left = current_vertice['left']
        right = current_vertice['right']

        if left != None:
            current_vertice = left

            if right != None:
                queue.put(( right, current_height ))
        elif right != None:
            current_vertice = right
        elif not queue.empty():
            current_vertice, current_height = queue.get()
        else:
            return height

def calculate_size(vertice):
    return calculate_width(vertice), calculate_height(vertice)

# рекурсивный расчёт координат вершин
def calculate_positions(vertice, offset_x = 0, offset_y = -1):
    if vertice == None: return

    # зачем-то ось Y направлена вверх, «против» графа, так что начнём отсчёт с
    # высоты и пойдём наверх
    if offset_y == -1: offset_y = calculate_height(vertice) - 1

    queue = Queue()
    current_vertice = vertice
    current_offset_x = offset_x
    current_offset_y = offset_y

    while True:
        # узкое место, подсчёт ширины для каждого потомка
        current_vertice['x'] = current_offset_x + calculate_width(current_vertice['left'])
        current_vertice['y'] = current_offset_y

        left = current_vertice['left']
        right = current_vertice['right']

        current_offset_y = current_offset_y - 1

        if left != None:
            if right != None:
                queue.put(( right, current_vertice['x'] + 1, current_offset_y ))
            current_vertice = left
        elif right != None:
            current_offset_x = current_vertice['x'] + 1
            current_vertice = right
        elif not queue.empty():
            current_vertice, current_offset_x, current_offset_y = queue.get()
        else:
            return

# красивенький вывод
# рекурсивен, так что не работает для больших деревьев
def print_in_order(vertice):
    # если координаты ещё не были рассчитаны, рассчитаем
    if not 'x' in vertice: calculate_positions(vertice)

    # размер графа
    height = calculate_height(vertice)
    width = calculate_width(vertice)

    if width > 120:
        print('graph is too big')
        return

    # создаём поле из «-1» размером с граф
    field = [ [ -1 for x in range(0, width) ] for x in
            list(range(0, calculate_height(vertice))) ]

    # рекурсивно отмечаем вершину на поле
    def mark_vertice(vertice):
        if vertice == None: return

        # опять же, переворачиваем ось Y
        field[height - 1 - vertice['y']][vertice['x']] = vertice['id']
        mark_vertice(vertice['left'])
        mark_vertice(vertice['right'])

    mark_vertice(vertice)

    # выводим поле (с пробелами вместо «-1»)
    print('\n'.join(''.join(
            ' ' if x == -1 else str(x) for x in y) for y in field))

# получаем координаты вершины
def get_position_of(vertice, id):
    if vertice == None: return None

    # если координаты ещё не были рассчитаны, рассчитаем
    if not 'x' in vertice: calculate_positions(vertice)

    queue = Queue()
    current_vertice = vertice

    while True:
        if current_vertice['id'] == id: return current_vertice['x'], current_vertice['y']

        left = current_vertice['left']
        right = current_vertice['right']

        if left != None:
            current_vertice = left
            if right != None:
                queue.put(right)
        elif right != None:
            current_vertice = right
        elif not queue.empty():
            current_vertice = queue.get()
        else:
            return None

root_vertice = solve_graph([
    [ 10, 5, 3 ],
    [ 2, 4 ],
    [ 4, 1 ],
    [ 0, 6 ],
    [ 7, 6 ],
    [ 8, 9 ],
    [ 4, 5 ],
    [ 6, 3 ],
    [ 3, 5 ],
    [ 3, 8 ]
])

print(root_vertice)
print(calculate_size(root_vertice))
print_in_order(root_vertice)
print(get_position_of(root_vertice, 1))
print(get_position_of(root_vertice, 3))
print(get_position_of(root_vertice, 9))

root_vertice = solve_graph(
    [ [ 1000, 15, 3 ] if x < 0 else [ x, x + 1 ] for x in range(-1, 999) ]
)


print(calculate_width(root_vertice))
print(calculate_height(root_vertice))
calculate_positions(root_vertice)

print(get_position_of(root_vertice, 15))
print(get_position_of(root_vertice, 9))