Граф — это множество вершин (обозначаются на схемах точками или кругами), некоторые из которых соединены между собой рёбрами (обозначаются на схемах линиями). Бинарным деревом называют такой граф, на который наложен ряд ограничений:
- граф не содержит циклов, т.е. в графе нет такой вершины, из которой, проходя по рёбрам графа, можно попасть в эту же вершину;
- граф является связным, т.е. из любой вершины графа можно попасть по рёбрам в любую другую;
- никакая вершина графа не может быть связана более чем с тремя другими вершинами;
- есть одна вершина, называемая корнем дерева, которая связана не более чем с двумя вершинами.
Примеры бинарных деревьев (корень показан как вершина с номером 1):
(тут должно быть изображение)
Будем называть высотой бинарного дерева максимальное возможное в этом дереве количество рёбер, которое может потребоваться пройти от корня дерева, чтобы добраться до какой-либо вершины графа (при этом нельзя дважды проходить через одно и то же ребро или одну и ту же вершину). На картинках выше изображены бинарные деревья высотой 2.
Петя и Витя решили сыграть в игру по строительству бинарного дерева. Перед началом игры в их бинарном дереве содержится ровно 1 вершина, являющаяся корнем этого дерева. В свой ход игрок на свой выбор добавляет в бинарное дерево либо одну вершину, связывая её ребром с одной из уже существующих в дереве вершин, либо две вершины, связывая их рёбрами также с одной из уже существующих в дереве вершин. При добавлении вершин и рёбер игроки не могут нарушать ограничений построения графа-бинарного дерева.
Примеры допустимых ходов (чёрным показан граф на момент начала хода игрока, зелёным выделены рёбра и вершины, которые он добавил в свой ход):
(тут должно быть изображение)
Назовём полным бинарным деревом высоты h такое бинарное дерево, в которое не может быть добавлена ни одна вершина с ребром так, чтобы высота дерева не увеличилась.
Победителем в игре будет считаться игрок, в чей ход бинарное дерево превратится в полное бинарное дерево высоты 12. Игроки также договорились, что ни в какой момент игры высота дерева не должна стать больше 12. Первым ходит Петя. Кто может победить в такой игре независимо от ходов противника?
В ответ запишите два числа через пробел без кавычек: номер игрока, который может победить независимо от ходов противника (1 — Петя, 2 — Витя) и максимальное количество ходов, которые может потребоваться выполнить этому игроку для победы. Пример записи ответа, если выиграть может Петя своим вторым ходом независимо от ходов противника: «1 2».