34504번 - Beautiful Bracelets 스페셜 저지다국어

Busy Beaver has collected some pairs of seashells, and he is trying to make them into two beautiful bracelets!

He has $N$ pairs of seashells, where both seashells in the $i$-th pair have type $a_i$. He wants to make two bracelets, such that each bracelet has one seashell from each pair. Busy Beaver decides his own metric for a beautiful pair of bracelets, which is minimizing the length of the longest common subsequence¹ between two bracelets.

Formally, let $s$ and $t$ be two permutations of the original array $a$. We want to find $(s,t)$ that minimizes the length of the longest cyclic common subsequence, $f(s,t)$, defined by the following:

• Consider all cyclic shifts of array $t$, denoted as $t_1,t_2,\dots,t_n$².
• Let $\text{LCS}(s,t)$ be the length of the Longest Common Subsequence between $s$ and $t$. Then $$f(s,t) = \max_{1\le i \le n}\text{LCS}(s,t_i).$$

Unfortunately, Busy Beaver has too many seashells to find the most beautiful bracelet pairs by hand. Please help him!

¹An array $s$ is a subsequence of an array $t$ if $s$ can be obtained from $t$ by deleting some (possibly none or all) elements from $t$, without reordering the remaining elements.

²A cyclic shift $t_i$ of an array $t=[t^{(1)},t^{(2)},\dots,t^{(n)}]$ by $i$ places is given by $[t^{(1+i)},t^{(2+i)},\dots,t^{(n+i)}]$, where indices are taken modulo $n$.

Each test contains multiple test cases. The first line of input contains a single integer $T$ $(1\le T\le 500)$, the number of test cases. The description of each test case follows.

The first line of each test case contains a single positive integer $N$ $(1\le N\le 500)$.

The second line of each test case contains $N$ integers $a_1,a_2,\dots, a_N$ $(1\le a_i\le 10^9)$ --- the types of seashells Busy Beaver has collected.

It is guaranteed that the sum of $N$ across all test cases does not exceed $500$.

For each test case, output two lines. The first line consists of $N$ integers $s_1,s_2,\dots,s_N$, and the second line consists of $N$ integers $t_1,t_2,\dots,t_N$, representing some $(s,t)$ that minimizes $f(s,t)$.

If there are multiple solutions, print any of them.

Note that $f([1,2,3],[1,3,2])$ is $2$ because $\text{LCS}([1,2,3],[1,3,2]) = 2$ ($[1,2]$ is a shared subsequence). This is the maximum $\text{LCS}$ over all cyclic shifts of $t$:

• $\text{LCS}([1,2,3],[1,3,2]) = 2$ ($[1,2]$ is a shared subsequence).
• $\text{LCS}([1,2,3],[3,2,1]) = 1$ ($[1]$ is a shared subsequence).
• $\text{LCS}([1,2,3],[2,1,3]) = 2$ ($[2,3]$ is a shared subsequence).

It can be shown that there are no $s$ and $t$ that are permutations of $[1,2,3]$, such that $f(s,t) \le 1$.