Tensor
Contest: Codeforces Round 948 (Div. 2)
Difficulty rating: 2600
Tags: constructive algorithms, graphs, interactive

This is an interactive problem.

You are given an integer $$$n$$$.

The jury has hidden from you a directed graph with $$$n$$$ vertices (numbered from $$$1$$$ to $$$n$$$) and some number of edges. You additionally know that:

- The graph only contains edges of the form $$$i \leftarrow j$$$, where $$$1 \le i < j \le n$$$.
- For any three vertices $$$1 \le i < j < k \le n$$$, at least one of the following holds$$$^\dagger$$$:   Vertex $$$i$$$ is reachable from vertex $$$j$$$, or  Vertex $$$i$$$ is reachable from vertex $$$k$$$, or  Vertex $$$j$$$ is reachable from vertex $$$k$$$.

You want to color each vertex in either black or white such that for any two vertices $$$i$$$ and $$$j$$$ ($$$1 \le i < j \le n$$$) of the same color, vertex $$$i$$$ is reachable from vertex $$$j$$$.

To do that, you can ask queries of the following type:

- ?  i  j — is vertex $$$i$$$ reachable from vertex $$$j$$$ ($$$1 \le i < j \le n$$$)?

Find any valid vertex coloring of the hidden graph in at most $$$2 \cdot n$$$ queries. It can be proven that such a coloring always exists.

Note that the grader is not adaptive: the graph is fixed before any queries are made.

$$$^\dagger$$$ Vertex $$$a$$$ is reachable from vertex $$$b$$$ if there exists a path from vertex $$$b$$$ to vertex $$$a$$$ in the graph.

Input format:
Each test contains multiple test cases. The first line of input contains a single integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases. The description of the test cases follows.

The only line of each test case contains a single integer $$$n$$$ ($$$3 \le n \le 100$$$) — the number of vertices in the hidden graph.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$1000$$$.

Interaction format:
The interaction for each test case begins by reading the integer $$$n$$$.

To make a query, output "? i j" without quotes ($$$1 \le i < j \le n$$$). If vertex $$$i$$$ is reachable from vertex $$$j$$$, you will get YES as an answer. Otherwise, you will get NO as an answer.

If you receive the integer $$$-1$$$ instead of an answer or a valid value of $$$n$$$, it means your program has made an invalid query, has exceeded the limit of queries, or has given an incorrect answer on the previous test case. Your program must terminate immediately to receive a Wrong Answer verdict. Otherwise, you can get an arbitrary verdict because your solution will continue to read from a closed stream.

When you are ready to give the final answer, output "! $$$c_1 \ c_2 \ \ldots \ c_n$$$" without quotes — the colors of the vertices, where $$$c_i = 0$$$ if the vertex is black, and $$$c_i = 1$$$ if the vertex is white. After solving all test cases, your program should be terminated immediately.

After printing a query, do not forget to output an end of line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use:

- fflush(stdout) or cout.flush() in C++;
- System.out.flush() in Java;
- flush(output) in Pascal;
- stdout.flush() in Python;
- see documentation for other languages.

Hacks

To hack, use the following format:

The first line contains an integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$3 \le n \le 100$$$, $$$0 \le m \le \frac{n\cdot(n - 1)}{2}$$$) — the number of vertices and edges in the graph.

Each of the following $$$m$$$ lines should contain two integers $$$a$$$ and $$$b$$$ ($$$1 \le b < a \le n$$$), indicating that there is the edge $$$a \rightarrow b$$$ in the graph. The graph should satisfy the conditions above.

The sum of $$$n$$$ over all test cases should not exceed $$$1000$$$.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
The hidden graph in the first test case:

The hidden graph in the second test case:

The interaction happens as follows:

SolutionJuryExplanation2There are $$$2$$$ test cases.4In the first test case, the graph has $$$4$$$ vertices.? 1 2 YESThe solution asks if vertex $$$1$$$ is reachable from vertex $$$2$$$, and the jury answers YES.? 2 3 YESThe solution asks if vertex $$$2$$$ is reachable from vertex $$$3$$$, and the jury answers YES.? 1 3 YESThe solution asks if vertex $$$1$$$ is reachable from vertex $$$3$$$, and the jury answers YES.? 1 4 NOThe solution asks if vertex $$$1$$$ is reachable from vertex $$$4$$$, and the jury answers NO.? 2 4 NOThe solution asks if vertex $$$2$$$ is reachable from vertex $$$4$$$, and the jury answers NO.? 3 4 NOThe solution asks if vertex $$$3$$$ is reachable from vertex $$$4$$$, and the jury answers NO.! 0 0 0 1The solution has somehow determined a valid coloring and outputs it. Since the output is correct, the jury continues to the next test case.5In the second test case, the graph has $$$5$$$ vertices.! 1 1 0 1 0The solution has somehow determined a valid coloring, and outputs it. Since the output is correct and there are no more test cases, the jury and the solution exit.

Note that the line breaks in the example input and output are for the sake of clarity, and do not occur in the real interaction.

Example input:
2
4

YES

YES

YES

NO

NO

NO

5

Example output:
? 1 2

? 2 3

? 1 3

? 1 4

? 2 4

? 3 4

! 0 0 0 1

! 1 1 0 1 0

Editorial:
Сначала поймем почему 2 цветов действительно достаточно.
Заметим, что отношение достижимости в графе задает Частично упорядоченное множество.
По теореме Дилуорса размер максимальной антицепи равен минимальному количеству цепей, покрывающих ЧУМ.
Заметим, что условие на достижимость пары вершин внутри любой тройки влечет ограничение на максимальный размер антицепи. Он просто не больше 2. Значит 2 цветов действительно достаточно.
Осталось понять как явно строить эти 2 цепи.
Будем строить индуктивно. Давайте поддерживать 3 стека  — последние вершины покрашенный в черный цвет, белый цвет и красный цвет соответсвенно. Они будут отвечать за строимые цепи.
Пусть мы построили цепи на $$$n$$$ вершинах и хотим построить на $$$n + 1$$$:
• Если белый или черный стеки пусты то просто добавим вершину $$$n+1$$$ в пустой стек.
• Если красный стек пустой:  Спросим про достижимость последних вершин из белого и черного стеков из вершины $$$n+1$$$.  Если достижимы обе вершины, то отправим вершину $$$n+1$$$ в красный стек.  Если достижима только 1 вершина то отправим вершину $$$n+1$$$ в стек, последняя вершина которого достижима из $$$n+1$$$.  Случай когда достижимо 0 вершин невозможен так как это противоречит условию.
• Спросим про достижимость последних вершин из белого и черного стеков из вершины $$$n+1$$$.
• Если достижимы обе вершины, то отправим вершину $$$n+1$$$ в красный стек.
• Если достижима только 1 вершина то отправим вершину $$$n+1$$$ в стек, последняя вершина которого достижима из $$$n+1$$$.
• Случай когда достижимо 0 вершин невозможен так как это противоречит условию.
• Если красный стек не пустой:  Спросим про достижимость последней вершины красного стека из вершины $$$n+1$$$.  Если она достижима, то отправим ее в красный стек  Если она не достижима, то сделаем вопрос про конец белого стека.  Если вершина из конца белого стека не достижима, то тогда обязана быть достижима вершина из конца черного стека, иначе происходит противоречие с условием задачи.  Покрасим вершину $$$n+1$$$ в черный стек, если достигается черная вершина или в белый стек, если достигается белая вершина.  Перекрасим все вершины из красного стека в противоположный цвет относительно $$$n+1$$$ вершины. Мы так можем сделать так как по построению все вершины белого и черного стеков достижимы из всех вершин красного стека.  не забудем очистить красный стек
• Спросим про достижимость последней вершины красного стека из вершины $$$n+1$$$.
• Если она достижима, то отправим ее в красный стек
• Если она не достижима, то сделаем вопрос про конец белого стека.
• Если вершина из конца белого стека не достижима, то тогда обязана быть достижима вершина из конца черного стека, иначе происходит противоречие с условием задачи.
• Покрасим вершину $$$n+1$$$ в черный стек, если достигается черная вершина или в белый стек, если достигается белая вершина.
• Перекрасим все вершины из красного стека в противоположный цвет относительно $$$n+1$$$ вершины. Мы так можем сделать так как по построению все вершины белого и черного стеков достижимы из всех вершин красного стека.
• не забудем очистить красный стек
При каждом добавлении новой вершины тратится не более 2 запросов. Тогда суммарно мы потратим не более $$$2 \cdot n$$$ вопросов.
В ходе алгоритма все операции производятся за O(1), тогда асимптотика $$$O(n)$$$.
В качестве упражнения читателю предлагается доказать нижнюю оценку на количество запросов.