Это интерактивная задача!
На последнем региональном этапе Хемосе, ЗейадХаттаб и ЯхиаШериф — члены команды Carpe Diem — не прошли отбор на ICPC по каким-то неизвестным причинам. Хемосе был очень расстроен и у него был плохой день после соревнований, но ЗейадХаттаб очень мудрый и хорошо знает Хемосе, и не хочет видеть его грустным.
Зейад знает, что Хемосе любит задачи с деревьями, поэтому он дал ему задачу с деревом с очень особенным устройством.
У Хемоса есть взвешенное дерево на \(n\) вершинах и \(n-1\) ребрах. К сожалению, Хемосе не помнит веса ребер.
Определим \(Dist(u, v)\) для \(u\neq v\) как наибольший общий делитель весов всех ребер на пути от вершины \(u\) к вершине \(v\).
У Хемосе есть специальное устройство. Хемосе может дать устройству набор вершин, и устройство вернет наибольший \(Dist\) между любыми двумя вершинами из этого набора. Более формально, если Хемосе даст устройству набор из \(S\) узлов, устройство вернет наибольшее значение \(Dist(u, v)\) по всем парам \((u, v)\), для которых \(u\), \(v\) \(\in\) \(S\) и \(u \neq v\).
Хемосе может использовать это устройство не более \(12\) раз, и хочет найти любые две различные вершины \(a\), \(b\) такие, что \(Dist(a, b)\) является максимально возможным. Можете ли вы ему помочь?
Протокол взаимодействия
Начните взаимодействие с чтения одного целого числа \(n\) (\(2 \le n \le 10^3\)) — количества вершин в дереве.
Затем прочитайте \(n-1\) строк.
\(i\)-я из следующих \(n-1\) строк содержит два целых числа \(u_i\) и \(v_i\) (\(1 \leq u_i, v_i \leq n\), \(u_i\neq v_i\)), что означает наличие ребра между вершинами \(u_i\) и \(v_i\).
Гарантируется, что веса ребер были \(\leq 10^9\).
Гарантируется, что данный граф является деревом.
Теперь вы можете начать задавать запросы. Чтобы задать запрос о множестве из \(k\) вершин \(v_1, v_2, \ldots, v_k\) (\(2 \le k \le n\), \(1 \le v_i \le n\), все \(v_i\) различны), выведите:
? \(k\) \(v_1\) \(v_2\) \(\ldots\) \(v_k\).
Вы получите целое число \(x\), наибольшее \(Dist(v_i, v_j)\) по \(1 \le i, j \le k\) с \(i \neq j\).
Когда вы найдете \(a\) и \(b\) (\(1 \le a, b \le n)\), \(a\neq b\)) такие, что \(Dist(a, b)\) является максимально возможным, выведите ответ в следующем формате:
! \(a\) \(b\)
Вывод ответа не учитывается в лимит в \(12\) запросов.
Если существует несколько пар \((a, b)\) с одинаковым наибольшим \(Dist(a, b)\), можно вывести любую.
После вывода запроса не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Решение «зависло». Для сброса буфера используйте:
- fflush(stdout) или cout.flush() в C++;
- System.out.flush() в Java;
- flush(output) в Pascal;
- stdout.flush() в Python;
- смотрите документацию для других языков.
Взломы
Чтобы взломать решение, используйте следующий формат.
Первая строка должна содержать одно целое число \(n\) \((2 \leq n \le 10^3)\) — количество вершин.
В \(i\)-й из следующих \(n-1\) строк должно содержаться три целых числа \(u_i\), \(v_i\), \(w_i\) (\(1 \le u_i, v_i \le n\), \(u_i\ne v_i\), \(1 \le w \le 10^9\)), что означает, что между вершинами \(u_i\) и \(v_i\) есть ребро с весом \(w_i\).
Эти \(n-1\) ребер должны образовывать дерево.