Это интерактивная задача.
У Алисы есть дерево \(T\), состоящее из \(n\) вершин, пронумерованных от \(1\) до \(n\). Алиса покажет дерево \(T\) Бобу. После того как Боб увидит \(T\), он должен назвать Алисе две перестановки \(p_1\) и \(p_2\) чисел \([1, 2, \ldots, n]\).
Затем Алиса сыграет \(q\) раундов следующей игры:
- Алиса создаст массив \(a\), который является перестановкой чисел \([0,1,\ldots,n-1]\). Значение вершины \(v\) будет равно \(a_v\).
- Алиса выберет две вершины \(u\) и \(v\) (\(1 \leq u, v \leq n\), \(u \neq v\)) из \(T\) и сообщит их Бобу. Бобу нужно будет найти \(\operatorname{MEX}^\dagger\) значений на единственном простом пути между вершинами \(u\) и \(v\).
- Чтобы найти это значение, Боб может задать Алисе не более \(5\) запросов. В каждом запросе Боб должен дать Алисе три целых числа \(t\), \(l\) и \(r\), таких, что \(t\) равно \(1\) или \(2\), и \(1 \leq l \leq r \leq n\). После этого Алиса сообщит Бобу величину, равную \(\)\min_{i=l}^{r} a[p_{t,i}].\(\)
Обратите внимание, что все раунды независимы друг от друга. В частности, значения \(a\), \(u\) и \(v\) могут быть разными в разных раундах.
Боб озадачен, поскольку он знает только решение с HLD, которое требует \(O(\log(n))\) запросов в каждом раунде. Поэтому ему нужна ваша помощь, чтобы выиграть игру.
\(^\dagger\) \(\operatorname{MEX}\) набора чисел \(c_1, c_2, \ldots, c_k\) определяется как наименьшее неотрицательное целое число \(x\), которое не встречается в наборе чисел \(c\).
Протокол взаимодействия
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число \(t\) (\(1 \leq t \leq 10^4\)) — количество наборов входных данных. Далее следует взаимодействие по каждому набору входных данных.
Первая строка каждого набора входных данных содержит два положительных целых числа \(n\) и \(q\) (\(2 \leq n \leq 10^5\), \(1 \leq q \leq 10^4\)) — количество вершин в \(T\) и количество раундов соответственно.
Следующие \(n-1\) строк содержат по два целых числа \(u\) и \(v\) (\(1 \leq u, v \leq n\), \(u \neq v\)), обозначающие ребро между вершинами \(u\) и \(v\). Гарантируется, что заданные ребра образуют дерево.
Гарантируется, что суммы \(n\) и \(q\) по всем наборам входных данных не превосходит \(10^5\) и \(10^4\) соответственно.
Также гарантируется, что сумма значений \(n \cdot q\) не превосходит \(3 \cdot 10^6\).
После завершения чтения ребер дерева необходимо вывести две перестановки \(p_1\) и \(p_2\) чисел \([1, 2, \ldots, n]\).
Для этого в отдельной строке выведите \(n\) целых чисел — перестановку \(p_1\).
В следующей строке выведите \(n\) целых чисел — перестановку \(p_2\).
Алиса начнет играть в игру.
Для каждого раунда необходимо считать два целых числа \(u\) и \(v\) (\(1 \leq u, v \leq n\), \(u \neq v\)). Вам нужно найти \(\operatorname{MEX}\) значений вершин на пути из \(u\) в \(v\).
Чтобы сделать запрос, выведите «? \(t\) \(l\) \(r\)» без кавычек, где \(t\) равно \(1\) или \(2\) и \(1 \leq l \leq r \leq n\). После этого вы должны прочитать одно целое число — ответ на ваш запрос \(\min_{i=l}^{r} a_{p_{t,i}}\). В каждом раунде можно сделать не более \(5\) таких запросов для каждого раунда.
Когда вы хотите вывести ответ, выведите «! \(x\)» (\(1 \leq x, y \leq n\)) без кавычек. После этого считайте одно целое число, которое в нормальной ситуации будет равно \(1\).
Если вместо корректного ответа вы получаете целое число \(-1\), это означает, что ваша программа сделала некорректный запрос, превысила лимит запросов или дала неправильный ответ на предыдущем наборе входных данных. Чтобы получить вердикт Неправильный ответ, ваша программа должна немедленно завершиться. В противном случае вы можете получить произвольный вердикт, поскольку ваше решение будет продолжать читать из закрытого потока.
После вывода запроса или ответа не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Решение «зависло». Для сброса буфера используйте:
- fflush(stdout) или cout.flush() в C++;
- System.out.flush() в Java;
- flush(output) в Pascal;
- stdout.flush() в Python;
- смотрите документацию для других языков.
Взломы
Чтобы сделать взлом, используйте следующий формат.
Первая строка должна содержать целое число \(t\) (\(1 \le t \le 10^4\)) — количество наборов входных данных.
Первая строка каждого набора входных данных должна содержать два целых числа \(n\) и \(q\) (\(2 \leq n \leq 10^5\); \(1 \leq q \leq 10^4\)) — количество вершин в \(T\) и количество раундов, соответственно.
Следующие \(n-1\) строк должны содержать по два целых числа \(u\) и \(v\) (\(1 \leq u, v \leq n\), \(u \neq v\)), означающие ребро между вершинами \(u\) и \(v\). Данные ребра должны образовывать дерево.
Для каждого из \(q\) раундов сначала выведите в отдельной строке перестановку чисел \([0, 1, 2, \ldots, n-1]\) — массив \(a\), который выберет Алиса в начале раунда.
В следующей строке выведите два различных целых числе \(u\) и \(v\) (\(1 \leq u, v \leq v\), \(u \neq v\)) — вершины, являющиеся концам пути, про который спросит Алиса.
Сумма значений \(n\) и сумма значений \(q\) по всем наборам входных данных не должны превышать \(10^5\) и \(10^4\) соответственно.
Сумма значений \(n \cdot q\) не должна превышать \(3 \cdot 10^6\).