Это интерактивная задача.

У Алисы есть дерево $$$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$$$.