G2. Бодлер (сложная версия)
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия задачи. Единственное отличие между двумя версиями заключается в том, что в сложной версии дерево может иметь любую форму.

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

Бодлер очень богат, поэтому он купил дерево размером $$$n$$$, корень которого находится в произвольной вершине. Кроме того, каждая вершина имеет значение $$$1$$$ или $$$-1$$$.

Коровка-Нерд увидела дерево и влюбилась в него. Однако компьютерные науки не приносят ей достаточно денег, поэтому она не может позволить себе его купить. Бодлер решил сыграть с Коровкой-Нерд в игру, и если она выиграет, он подарит ей дерево.

Коровка-Нерд не знает, какая вершина является корнем, и она также не знает значений вершин. Однако она может задавать Бодлеру запросы двух типов:

  • $$$1$$$ $$$k$$$ $$$u_1$$$ $$$u_2$$$ $$$...$$$ $$$u_k$$$: Пусть $$$f(u)$$$ — это сумма значений всех вершин на пути от корня дерева до вершины $$$u$$$. Коровка-Нерд может выбрать целое число $$$k$$$ $$$(1 \le k \le n)$$$ и $$$k$$$ вершин $$$u_1, u_2, ..., u_k$$$, и она получит значение $$$f(u_1) + f(u_2) + ... + f(u_k)$$$.
  • $$$2$$$ $$$u$$$: Бодлер изменит значение вершины $$$u$$$. В частности, если значение $$$u$$$ равно $$$1$$$, оно станет $$$-1$$$, и наоборот.

Коровка-Нерд выигрывает, если она правильно угадает значение каждой вершины (значения финального дерева, после выполнения запросов) за $$$n + 200$$$ запросов. Можете ли вы помочь ей выиграть?

Входные данные

Первая строка входных данных содержит одно целое число $$$t$$$ $$$(1 \le t \le 100)$$$ — количество наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ $$$(2 \le n \le 10^3)$$$ — размер дерева.

Каждая из следующих $$$n-1$$$ строк содержит два целых числа $$$u$$$ и $$$v$$$ $$$(1 \le u, v \le n, u \neq v)$$$, обозначающих ребро между вершинами $$$u$$$ и $$$v$$$ в дереве.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$10^3$$$ и что каждый предоставленный граф является деревом.

Протокол взаимодействия

Чтобы задать запрос типа $$$1$$$, выведите строку в следующем формате (без кавычек):

  • "? 1 k $$$u_1$$$ $$$u_2$$$ $$$...$$$ $$$u_k$$$", ($$$1 \le k, u_i \le n$$$)

Жюри вернет одно целое число, $$$f(u_1) + f(u_2) + ... + f(u_k)$$$.

Чтобы задать запрос типа $$$2$$$, выведите строку в следующем формате:

  • "? 2 $$$u$$$" ($$$1 \le u \le n$$$)

Жюри изменит значение вершины $$$u$$$: если его значение равно $$$1$$$, оно станет $$$-1$$$, и наоборот.

Когда вы найдете ответ, выведите одну строку в следующем формате:

  • "! $$$v_1, v_2, ..., v_n$$$" ($$$v_i = 1$$$ или $$$v_i = -1$$$, и $$$v_i$$$ — значение вершины $$$i$$$ после выполнения запросов)

После этого продолжайте обрабатывать следующий набор входных данных или завершите программу, если это был последний набор входных данных. Печать ответа не считается запросом.

Интерактор не адаптивен, что означает, что значения дерева известны до того, как участник задает запросы.

Если ваша программа сделает более $$$n + 200$$$ запросов, ваша программа должна немедленно завершиться, чтобы получить вердикт Неправильный ответ. В противном случае вы можете получить произвольный вердикт, потому что ваше решение продолжит читать из закрытого потока.

После вывода запроса не забудьте вывести конец строки и сбросить вывод. В противном случае вы можете получить вердикт Превышен лимит бездействия. Для этого используйте:

  • fflush(stdout) или cout.flush() в C++
  • System.out.flush() в Java;
  • flush(output) в Pascal;
  • stdout.flush() в Python;
  • смотрите документацию для других языков.

Хаки

Для хаков используйте следующий формат.

Первая строка должна содержать одно целое число $$$t$$$ $$$(1 \le t \le 100)$$$ — количество наборов входных данных.

Первая строка каждого набора входных данных должна содержать ровно два целых числа $$$n$$$ и $$$root$$$ $$$(2 \le n \le 10^3, 1 \le root \le n)$$$ — размер дерева и корень дерева.

Вторая строка каждого набора входных данных должна содержать ровно $$$n$$$ целых чисел $$$a_1, a_2, ..., a_n$$$ $$$(|a_i| = 1)$$$ — где $$$a_i$$$ — значение вершины $$$i$$$.

Каждая из следующих $$$n-1$$$ строк должна содержать ровно два целых числа $$$u$$$ и $$$v$$$ $$$(1 \le u, v \le n)$$$ — обозначающих ребро дерева между вершинами $$$u$$$ и $$$v$$$.

Сумма $$$n$$$ по всем наборам входных данных не должна превышать $$$10^3$$$, и каждый предоставленный граф должен быть допустимым деревом.

Пример
Входные данные
3
4
1 4
4 2
2 3

1

-1


-5

-5

2
1 2

2

7
1 2
2 7
7 3
7 4
7 5
7 6

-1
Выходные данные





? 1 3 1 2 4

? 1 2 3 1

? 2 4
? 1 3 1 2 4

? 1 2 3 1

! -1 -1 -1 -1


? 1 1 1

! 1 1






? 1 1 1

! -1 1 1 1 1 1 -1
Примечание

В первом примере корнем дерева является вершина $$$4$$$, а значения: $$$[-1, -1, -1, 1]$$$ (значение $$$i$$$-й вершины — это значение вершины $$$i$$$).

Изначально $$$f(1) = 0, f(2) = 0, f(3) = -1, f(4) = 1$$$. Поэтому ответ на наш первый запрос — это $$$f(1) + f(2) + f(4) = 1$$$, а на второй запрос — это $$$f(3) + f(1) = -1$$$.

После изменения значения вершины $$$4$$$ значения становятся $$$[-1, -1, -1, -1]$$$. Кроме того, $$$f(1) = -2, f(2) = -2, f(3) = -3, f(4) = -1$$$. Поэтому $$$f(1) + f(2) + f(4) = -5$$$ и $$$f(3) + f(1) = -5$$$.

Мы отвечаем, что финальные значения вершин равны $$$[-1, -1, -1, -1]$$$, что верно. Обратите внимание, что мы сообщаем значения вершин после изменений, а не до.

Во втором примере корнем дерева является $$$2$$$, а начальные значения равны $$$[1, 1]$$$.

В последнем примере корнем дерева является $$$1$$$, а начальные значения равны $$$[-1, 1, 1, 1, 1, 1, -1]$$$.

Обратите внимание, что это всего лишь объяснение того, как работают запросы, и оно не должно использовать какую-либо конкретную стратегию для решения задачи.