E. Тензор
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

Вам дано целое число $$$n$$$.

Жюри загадало ориентированный граф с $$$n$$$ вершинами (пронумерованными от $$$1$$$ до $$$n$$$) и с некоторым количеством рёбер. Дополнительно известно, что:

  • Граф содержит рёбра только вида $$$i \leftarrow j$$$, где $$$1 \le i < j \le n$$$.
  • Для любых трёх вершин $$$1 \le i < j < k \le n$$$ верно хотя бы одно из следующего$$$^\dagger$$$:
    • Вершина $$$i$$$ достижима из вершины $$$j$$$, или
    • Вершина $$$i$$$ достижима из вершины $$$k$$$, или
    • Вершина $$$j$$$ достижима из вершины $$$k$$$.

Вы хотите покрасить каждую вершину графа либо в белый, либо в чёрный цвет так, чтобы для любых двух вершин $$$i$$$ и $$$j$$$ ($$$1 \le i < j \le n$$$) одного цвета вершина $$$i$$$ была достижима из вершины $$$j$$$.

Для этого вы можете делать запросы следующего вида:

  • ? i j — достижима ли вершина $$$i$$$ из вершины $$$j$$$ ($$$1 \le i < j \le n$$$)?

Найдите любую подходящую раскраску вершин графа за не более чем $$$2 \cdot n$$$ запросов. Можно доказать, что такая раскраска всегда существует.

Примечание: интерактор не является адаптивным, то есть граф фиксируется до выполнения каких-либо запросов.

$$$^\dagger$$$ Вершина $$$a$$$ достижима из вершины $$$b$$$ если в графе существует путь из вершины $$$b$$$ в вершину $$$a$$$.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Единственная строка каждого набора входных данных содержит единственное целое число $$$n$$$ ($$$3 \le n \le 100$$$) — количество вершин в графе.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$1000$$$.

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

Взаимодействие для каждого набора входных данных начинается с чтения целого числа $$$n$$$.

Для формирования запроса выведите «? i j» без кавычек ($$$1 \le i < j \le n$$$). Если вершина $$$i$$$ достижима из вершины $$$j$$$, вы получите в ответ YES. Иначе, вы получите в ответ NO.

Если вместо ответа или допустимого значения $$$n$$$ вы получите целое число $$$-1$$$, то это означает, что ваша программа сделала некорректный запрос, превысила лимит запросов или дала неверный ответ на предыдущем наборе входных данных. При получении вердикта «Неправильный ответ» ваша программа должна немедленно завершиться. В противном случае можно получить произвольный вердикт, поскольку решение будет продолжать считывать данные из закрытого потока.

Когда вы будете готовы дать окончательный ответ, выведите «! $$$c_1 \ c_2 \ \ldots \ c_n$$$» без кавычек — раскраска вершин графа, где $$$c_i = 0$$$, если вершина чёрная, и $$$c_i = 1$$$, если вершина белая. После решения одного набора входных данных программа должна сразу же переходить к следующему. После решения всех наборов входных данных программа должна быть немедленно завершена.

После вывода запроса не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Решение «зависло». Для сброса буфера используйте:

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

Взломы

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

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

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$3 \le n \le 100$$$, $$$0 \le m \le \frac{n\cdot(n - 1)}{2}$$$) — количество вершин и рёбер в графе.

Следующие $$$m$$$ строк должны содержать два числа $$$a$$$ и $$$b$$$ ($$$1 \le b < a \le n$$$), означающие, что в графе присутствует ребро $$$a \rightarrow b$$$. Граф должен удовлетворять условиям выше.

Сумма $$$n$$$ по всем наборам входных данных не должна превышать $$$1000$$$.

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

YES

YES

YES

NO

NO

NO

5

Выходные данные
? 1 2

? 2 3

? 1 3

? 1 4

? 2 4

? 3 4

! 0 0 0 1

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

Граф в первом примере:

Граф во втором примере:

Взаимодействие происходит следующим образом:

РешениеЖюриОбъяснение
2Есть $$$2$$$ набора входных данных.
4В первом наборе входных данных загадан граф с $$$4$$$-мя вершинами.
? 1 2 YESРешение спрашивает, достижима ли вершина $$$1$$$ из вершины $$$2$$$, жюри отвечает YES.
? 2 3 YESРешение спрашивает, достижима ли вершина $$$2$$$ из вершины $$$3$$$, жюри отвечает YES.
? 1 3 YESРешение спрашивает, достижима ли вершина $$$1$$$ из вершины $$$3$$$, жюри отвечает YES.
? 1 4 NOРешение спрашивает, достижима ли вершина $$$1$$$ из вершины $$$4$$$, жюри отвечает NO.
? 2 4 NOРешение спрашивает, достижима ли вершина $$$2$$$ из вершины $$$4$$$, жюри отвечает NO.
? 3 4 NOРешение спрашивает, достижима ли вершина $$$3$$$ из вершины $$$4$$$, жюри отвечает NO.
! 0 0 0 1Решение каким-то образом определило, что такая раскраска подходит, и выводит её. Поскольку ответ правильный, жюри переходит к следующему набору входных данных.
1Во втором наборе входных данных загадан граф с $$$5$$$-ю вершинами.
! 1 1 0 1 0Решение каким-то образом определило, что такая раскраска подходит, и выводит её. Поскольку ответ верен и наборов входных данных больше нет, жюри и решение завершаются.

Обратите внимание, что пустые строки во входных и выходных данных примера сделаны для наглядности и не встречаются в реальном взаимодействии.