D2. Вес перестановки (сложная версия)
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия задачи. Разница между простой и сложной версиями в том, что в этой версии вы должны вывести лексикографически минимальную перестановку с наименьшим весом.

Вам дана перестановка $$$p_1, p_2, \ldots, p_n$$$ целых чисел от $$$1$$$ до $$$n$$$.

Определим вес перестановки $$$q_1, q_2, \ldots, q_n$$$ целых чисел от $$$1$$$ до $$$n$$$ как $$$$$$|q_1 - p_{q_{2}}| + |q_2 - p_{q_{3}}| + \ldots + |q_{n-1} - p_{q_{n}}| + |q_n - p_{q_{1}}|$$$$$$

Вы хотите, чтобы ваша перестановка была как можно легче. Среди перестановок $$$q$$$ с наименьшим возможным весом найдите лексикографически минимальную.

Перестановка $$$a_1, a_2, \ldots, a_n$$$ называется лексикографически меньшей, чем перестановка $$$b_1, b_2, \ldots, b_n$$$, если существует некоторое $$$1 \le i \le n$$$ такое, что $$$a_j = b_j$$$ для всех $$$1 \le j < i$$$ и $$$a_i<b_i$$$.

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

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

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$2 \le n \le 200$$$)  — размер перестановки.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$, все $$$p_i$$$ различны)  — элементы перестановки.

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

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

Для каждого набора входных данных выведите $$$n$$$ целых чисел $$$q_1, q_2, \ldots, q_n$$$ ($$$1 \le q_i \le n$$$, все $$$q_i$$$ различны)  — одну из перестановок с наименьшим весом.

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

В первом наборе входных данных есть две перестановки длины $$$2$$$: $$$(1, 2)$$$ и $$$(2, 1)$$$. Перестановка $$$(1, 2)$$$ имеет вес $$$|1 - p_2| + |2 - p_1| = 0$$$, а перестановка $$$(2, 1)$$$ имеет тот же вес: $$$|2 - p_1| + |1 - p_2| = 0$$$. В этой версии мы должны вывести лексикографически меньшую из них  — $$$(1, 2)$$$.

Во втором наборе входных данных вес перестановки $$$(1, 3, 4, 2)$$$ равен $$$|1 - p_3| + |3 - p_4| + |4 - p_2| + |2 - p_1| = |1 - 1| + |3 - 4| + |4 - 3| + |2 - 2| = 2$$$. Перестановок с меньшими весами не существует.

В третьем наборе входных данных вес перестановки $$$(1, 3, 4, 2, 5)$$$ равен $$$|1 - p_3| + |3 - p_4| + |4 - p_2| + |2 - p_5| + |5 - p_1| = |1 - 3| + |3 - 2| + |4 - 4| + |2 - 1| + |5 - 5| = 4$$$. Перестановок с меньшими весами не существует.