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

Это простая версия задачи. Единственное отличие между двумя версиями заключается в том, что в этой версии гарантируется, что каждая вершина имеет общее ребро с вершиной $$$1$$$.

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

Бодлер очень богат, поэтому он купил дерево размером $$$n$$$, корнем которого является произвольная вершина. Кроме того, каждая вершина имеет значение $$$1$$$ или $$$-1$$$. В этой версии гарантируется, что каждая вершина смежна с вершиной $$$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$$$ в дереве. В этой версии гарантируется, что либо $$$u = 1$$$, либо $$$v = 1$$$.

Гарантируется, что сумма $$$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$$$, и каждый предоставленный граф должен быть допустимым деревом. Для этой версии каждая вершина должна быть смежна с вершиной $$$1$$$.

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

0


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





? 1 3 1 2 3

? 2 2
? 1 3 1 2 3

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

В примере корень дерева — это вершина $$$2$$$, а значения вершин равны $$$[-1, 1, -1, 1]$$$. Поэтому $$$f(1) = 0, f(2) = 1, f(3) = -1, f(4) = 1$$$.

Сначала мы запрашиваем сумму $$$f(1) + f(2) + f(3)$$$, поэтому мы получаем значение $$$0$$$. Затем мы переключаем значение вершины $$$2$$$, и значения становятся: $$$[-1, -1, -1, 1]$$$. Поэтому $$$f(1) = -2, f(2) = -1, f(3) = -3, f(4) = -1$$$, и $$$f(1) + f(2) + f(3) = -6$$$.

Наконец, мы понимаем, что значения вершин равны $$$[-1, -1, -1, 1]$$$, поэтому мы отвечаем на это.

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