← 返回题目列表

Codeforces · 1685/D1

D1. 排列权重(简单版)

中文机器翻译题面 查看原题

这是问题的简单版本。简单版本和困难版本之间的区别在于,在这个版本中,您可以输出具有最小权重的任何排列。

给你一个从 $$$1$$$ 到 $$$n$$$ 的整数排列 $$$p_1, p_2, \ldots, p_n$$$。

让我们定义 $$$1$$$ 到 $$$n$$$ 整数的排列 $$$q_1, q_2, \ldots, q_n$$$ 的权重为 $$$$$$|q_1 - p_{q_{2}}| + |q_2 - p_{q_{3}}| + \dots + |q_{n-1} - p_{q_{n}}| + |q_n - p_{q_{1}}|$$$$$$

您希望排列尽可能轻量。找到具有最小可能权重的任何排列$$$q$$$。

输入

输入的第一行包含一个整数 $$$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$$$ 都是不同的) — 具有最小权重的排列之一。

示例

输入 #1

3
2
2 1
4
2 3 1 4
5
5 4 3 2 1

输出 #1

1 2 
1 3 4 2 
1 4 2 3 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, 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, 4, 2, 3, 5)$$$ 的权重为 $$$|1 - p_4| + |4 - p_2| + |2 - p_3| + |3 - p_5| + |5 - p_1| = |1 - 2| + |4 - 4| + |2 - 3| + |3 - 1| + |5 - 5| = 4$$$。不存在权重较小的排列。