Это интерактивная задача.
Вам задано дерево — связный неориентированный граф без циклов. В нём загадали одну из вершин. Вы можете задавать вопросы интерактору: за один вопрос вы можете выбрать ребро и узнать, какой из двух концов ребра находится ближе к загаданной вершине, то есть, до какого из двух концов меньше кратчайшее расстояние от загаданной вершины. Вам требуется определить загаданную вершину за минимальное для данного дерева число запросов в худшем случае.
Обратите внимание, что загаданная вершина может быть не фиксирована интерактором заранее: в зависимости от ваших запросов он может менять её на любую другую, с условием, что это не противоречит ответам на предыдущие запросы.
В первой строке входных данных содержится целое число $$$n$$$ ($$$2 \le n \le 100$$$) — количество вершин в дереве.
В каждой из следующих $$$n-1$$$ строк записаны два целых числа $$$u$$$ и $$$v$$$ ($$$1 \le u, v \le n$$$), обозначающих ребро между вершинами $$$u$$$ и $$$v$$$. Гарантируется, что данные ребра образуют дерево.
После считывания выходных данных вы можете отправлять интерактору запросы двух типов:
После каждого вопроса не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Idleness Limit Exceeded или Превышено реальное время работы. Для сброса буфера вы можете использовать:
В случае, если вы сделаете большее число запросов, чем может быть необходимо для данного дерева в худшем случае, вы получите вердикт Неправильный ответ.
5 1 2 2 3 3 4 4 5 3 2 1
? 3 4 ? 2 3 ? 1 2 ! 1
5 2 1 3 1 4 1 5 1 1 1 4
? 1 2 ? 1 3 ? 1 4 ! 4
Взломы в данной задаче запрещены.
Название |
---|