Это интерактивная задача.
Вам дано целое число \(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\).
Протокол взаимодействия
Взаимодействие для каждого набора входных данных начинается с чтения целого числа \(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 | Есть \(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 | | Решение каким-то образом определило, что такая раскраска подходит, и выводит её. Поскольку ответ верен и наборов входных данных больше нет, жюри и решение завершаются. |
Обратите внимание, что пустые строки во входных и выходных данных примера сделаны для наглядности и не встречаются в реальном взаимодействии.