Это легкая версия задачи. Единственное отличие — это ограничение на количество запросов.
Это интерактивная задача.
Вам дано дерево из \(n\) вершин с вершиной \(1\) в качестве корневой.
В одной из вершин спрятан крот. Чтобы найти его положение, вы можете выбрать вершину \(x\) (\(1 \le x \le n\)) и сделать запрос к жюри. После этого жюри вернет \(1\), если крот находится в поддереве вершины \(x\). В противном случае жюри вернет \(0\). Если жюри возвращает \(0\) и крот не находится в корневой вершине \(1\), крот переместится в вершину-родителя той вершины, в которой он находится в данный момент.
Используя не более \(300\) операций, найдите текущую вершину, в которой находится крот.
Протокол взаимодействия
Первая строка каждого набора входных данных содержит одно целое число \(n\) (\(2 \le n \le 5000\)).
Следующая \(n-1\) строка описывает ребра дерева. Каждая строка содержит два целых числа, разделенные пробелом, \(u_i\) и \(v_i\) (\(1 \le u_i, v_i \le n\)), обозначающие ребро между вершинами \(u_i\) и \(v_i\).
Гарантируется, что входные данные представляют собой дерево.
Интерактор в этой задаче не является адаптивным. Другими словами, вершина, где изначально находится крот, зафиксирована в каждом наборе входных данных и не меняется во время взаимодействия.
Чтобы сделать запрос, вам нужно выбрать вершину \(x\) (\(1 \le x \le n\)) и вывести строку следующего вида:
После этого вы получите:
- \(0\), если крот не находится в поддереве \(x\);
- \(1\), если крот находится в поддереве \(x\).
Вы можете сделать не более \(300\) запросов такого вида для каждого набора входных данных.
Затем, если вы определили текущую вершину, где находится крот, выведите строку следующего вида:
Обратите внимание, что эта строка не считается запросом и не учитывается при подсчете количества заданных запросов.
После этого переходите к следующему набору входных данных.
Если вы сделаете более \(300\) запросов во время взаимодействия, ваша программа должна немедленно завершиться, и вы получите вердикт Неправильный ответ. В противном случае вы можете получить произвольный вердикт, потому что ваше решение будет продолжать читать из закрытого потока.
После вывода запроса не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Решение «зависло». Для сброса буфера используйте:
- fflush(stdout) или cout.flush() в C++;
- System.out.flush() в Java;
- flush(output) в Pascal;
- stdout.flush() в Python;
- смотрите документацию для других языков.
Взломы
Чтобы сделать взлом, используйте следующий формат:
Первая строка содержит количество наборов входных данных \(t\) (\(1 \le t \le 100\)). Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит два целых числа \(n\) и \(x\) (\(2 \le n \le 5000\), \(1 \le x \le n\)), описывающие размер дерева и начальное положение крота.
Следующая \(n-1\) строка описывает ребра дерева. Каждая строка содержит два целых числа, разделенные пробелом, \(u_i\) и \(v_i\) (\(1 \le u_i, v_i \le n\)), обозначающие ребро между вершинами \(u_i\) и \(v_i\).
Входные данные обязаны представлять собой дерево.
Примечание
В первом наборе входных данных крот изначально находится в вершине \(2\).
Для запроса «? 2», жюри возвращает \(1\), потому что крот находится в поддереве вершины \(2\). После этого запроса крот не перемещается.
Ответ \(2\) — это текущая вершина, где находится крот, поэтому ответ считается правильным.
Во втором наборе входных данных крот изначально находится в вершине \(6\).
Для запроса «? 2», жюри возвращает \(0\), потому что крот не находится в поддереве вершины \(2\). После этого запроса крот перемещается из вершины \(6\) в вершину \(5\).
Для запроса «? 6», жюри возвращает \(0\), потому что крот не находится в поддереве вершины \(6\). После этого запроса крот перемещается из вершины \(5\) в вершину \(4\).
Для запроса «? 4», жюри возвращает \(1\), потому что крот находится в поддереве вершины \(4\). После этого запроса крот не перемещается.
Ответ \(4\) — это текущая вершина, где находится крот, поэтому ответ считается правильным.
Обратите внимание, что приведенный пример предназначен только для понимания условия, и запросы в примере не гарантируют определение уникального положения крота.