Коровы вознамерились разработать собственной поисковик. К несчастью, они не имели опыта разработки больших программных продуктов и потому количество сотрудников их проекта \(N\) (\(1 \le N \le 10^{100}\)) стало существенно больше, чем изначально планировалось.
Для того, чтобы найти подходящее имя для своей компании, они решили оттолкнуться от верхней границы количества сотрудников своей компании и назвались
"Googol", что является названием числа \(10^{100}\).
В попытке улучшить управленческую структуру в компании, коровы структурировали её в виде двоичного дерева, где каждый сотрудник отвечает за управление своим двумя непосредственными подчинёнными " левым " и " правым ". Кроме того, для того чтобы сбалансировать нагрузку на каждого работника, коровы организовали структуру дерева так, чтобы для каждого сотрудника E, общее количество сотрудников в левом поддереве E было равно или больше чем количество сотрудников в правом поддереве.
Каждый сотрудник имеет уникальной ID - число в диапазоне \(1\ldots N\), с корнем дерева - сотрудником номер 1.
Вы можете интерактивно запрашивать у сотрудника ID двух его подчинённых.
Это делается выводом ID этого сотрудника в стандартный вывод, за которым следует перевод строки. В ответ Вы получите одну строку, которая содержит два целых числа - ID левого и правого подчинённых данного сотрудника. Оба этих числа могут быть равны 0, если у него нет ни одного подчинённого. Или только второе число может быть 0, если у него нет правого подчинённого. (Заметим, в что в соответствии с правилом балансирования, левое поддерево всегда больше или равно правом, и потому не возможна ситуация, когда у сотрудника есть правый подчинённый, но нет левого подчинённого).
К несчастью, коровы потеряли точное значение \(N\)
Пожалуйста, вычислите это число и выведите "Answer N",
а за ним перевод строки как последнюю строку вашего вывода.
Ваша программа имеет право сделать не более 70,000 запросов и не может выполняться боле 4 секунд (8 для Java и Python).
Далее приведен пример возможного взаимодействия между Вашей программой и грейдером (оценивающей программой).
YOUR PROGRAM: 1
GRADER: 4 3
YOUR PROGRAM: 4
GRADER: 2 0
YOUR PROGRAM: 3
GRADER: 0 0
YOUR PROGRAM: Answer 4
Дерево, соответствующее этому взаимодействию
1
4 3
2
Заметим, что нет необходимости спрашивать о детях для узла 2, поскольку мы можем логически вывести, что у него нет детей из того факта, что у вершины 4 нет правого потомка.