Это интерактивная задача.
Очистив Прибрежную Зону, Гретель обнаружила монстра по имени Генокракен и удерживает его для своих научных исследований.
Нервная система монстра может быть представлена как дерево\(^{\dagger}\) из \(n\) вершин (на самом деле, всё не должно постоянно напоминать деревья\(\ldots\)), пронумерованных от \(0\) до \(n-1\), с вершиной \(0\) в качестве корня.
Цель Гретель — узнать точную структуру нервной системы монстра. Более конкретно, она хочет узнать значения \(p_1, p_2, \ldots, p_{n-1}\) дерева, где \(p_i\) (\(0 \le p_i < i\)) является прямым предком вершины \(i\) (\(1 \le i \le n - 1\)).
Она не знает точно, как расположены вершины, но знает несколько приятных фактов:
- Если мы удалим корневую вершину \(0\) и все смежные ребра, то это дерево превратится в лес, состоящий только из путей\(^{\ddagger}\). Каждая вершина, которая изначально была смежной с вершиной \(0\), будет концом какого-то пути.
- Вершины нумеруются таким образом, что если \(1 \le x \le y \le n - 1\), то \(p_x \le p_y\).
- Вершина \(1\) гарантированно имеет ровно две смежные вершины (включая вершину \(0\)).
 |  |  |
| Дерево на этой картинке не удовлетворяет условию, потому что если мы удалим вершину \(0\), то вершина \(2\) (которая изначально была смежной с вершиной \(0\)) не будет концом пути \(4-2-5\). | Дерево на этой картинке не удовлетворяет условию, потому что должно выполняться \(p_3 \le p_4\). | Дерево на этой картинке не удовлетворяет условию, потому что вершина \(1\) имеет только одну смежную вершину. |
Гретель может делать запросы к защитной камере:
- «? a b» (\(1 \le a, b < n\), \(a \ne b\)) — камера проверит, содержит ли простой путь между вершинами \(a\) и \(b\) вершину \(0\).
Однако, чтобы избежать неожиданных последствий от чрезмерной стимуляции существа, Гретель хочет сделать не более \(2n - 6\) запросов. Хотя Гретель одарена, она не может сделать всё сразу, так что можете ли вы протянуть ей руку помощи?
\(^{\dagger}\)Дерево — это связный граф, в котором каждая пара различных вершин имеет ровно один простой путь, соединяющий их.
\(^{\ddagger}\)Путь — это дерево, вершины которого могут быть записаны в порядке \(v_1, v_2, \ldots, v_k\) так, что рёбра имеют вид \((v_i, v_{i+1})\) (\(1 \le i < k\)).
Протокол взаимодействия
Для каждого набора входных данных взаимодействие начинается с чтения целого числа \(n\).
Затем вы можете делать запросы следующего вида:
- «? a b» (без кавычек) (\(1 \le a, b < n\), \(a \ne b\)).
После запроса прочитайте целое число \(r\) — ответ на ваш запрос. Вам разрешено использовать не более \(2n - 6\) запросов этого типа.
- Если простой путь между вершинами \(a\) и \(b\) не содержит вершину \(0\), вы получите \(r = 0\).
- Если простой путь между вершинами \(a\) и \(b\) содержит вершину \(0\), вы получите \(r = 1\).
- В случае, если вы сделаете более \(2n-6\) запросов или сделаете некорректный запрос, вы получите \(r = -1\). После получения такого ответа ваша программа должна немедленно завершиться, чтобы получить вердикт «Неправильный ответ». В противном случае вы можете получить произвольный вердикт, потому что ваше решение продолжит чтение из закрытого потока.
Когда вы определите структуру, выведите строку в формате «! \(p_1 \space p_2 \ldots p_{n-1}\)» (без кавычек), где \(p_i\) (\(0 \le p_i < i\)) обозначает индекс прямого предка вершины \(i\). Этот запрос не учитывается в лимите \(2n - 6\) запросов.
После решения одного набора входных данных программа должна сразу же переходить к следующему. После решения всех наборов входных данных программа должна быть немедленно завершена.
После вывода любого запроса не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Решение «зависло». Для сброса буфера используйте:
- fflush(stdout) или cout.flush() в C++;
- System.out.flush() в Java;
- flush(output) в Pascal;
- stdout.flush() в Python;
- смотрите документацию для других языков.
Интерактор неадаптивный. Дерево не меняется в процессе взаимодействия.
Взломы
Для взлома используйте следующий формат:
Первая строка содержит одно целое число \(t\) (\(1 \le t \le 500\)) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит одно целое число \(n\) (\(4 \le n \le 10^4\)) — количество вершин в нервной системе Генокракена.
Вторая строка каждого набора входных данных содержит \(n-1\) целых чисел \(p_1, p_2, \ldots, p_{n-1}\) (\(0 \le p_1 \le p_2 \le \ldots \le p_{n-1} \le n - 2\), \(0 \le p_i < i\)) — прямые предки вершин \(1\), \(2\), ..., \(n-1\) в системе соответственно.
В каждом наборе входных данных значения \(p_1, p_2, \ldots, p_{n-1}\) должны обеспечивать следующее в дереве:
- Если мы удалим корневую вершину \(0\) и все смежные ребра, то это дерево превратится в лес, состоящий только из путей. Каждая вершина, которая изначально была смежной с вершиной \(0\), будет концом какого-то пути.
- Вершина \(1\) имеет ровно две смежные вершины (включая вершину \(0\)).
Сумма \(n\) по всем наборам входных данных не должна превышать \(10^4\).
Примечание
В первом наборе входных данных нервная система Генокракена образует следующее дерево:
- Ответ на «? 2 3» равен \(1\). Это означает, что простой путь между вершинами \(2\) и \(3\) содержит вершину \(0\).
Во втором наборе входных данных нервная система Генокракена образует следующее дерево:
- Ответ на «? 2 3» равен \(1\). Это означает, что простой путь между вершинами \(2\) и \(3\) содержит вершину \(0\).
- Ответ на «? 2 4» равен \(0\). Это означает, что простой путь между вершинами \(2\) и \(4\) не содержит вершину \(0\).
В третьем наборе входных данных нервная система Генокракена образует следующее дерево:
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
4
1
5
1
0
9
|
? 2 3
! 0 0 1
? 2 3
? 2 4
! 0 0 1 2
! 0 0 0 1 3 5 6 7
|