P5799 [SEERC 2019] Cycle String?

The Archmage gave Alice and Bob a cyclic string of length $2 \cdot n$. In this cyclic string, there are no repeated substrings of length $n$. In a cyclic string, the character $s_{i+1}$ comes after $s_i$, and $s_1$ comes after $s_{2n}$. Unfortunately, the devil scrambled the order of the characters in the string. Help Alice and Bob restore the string to an original string that satisfies the requirement above.

The first line contains a string $s$ of length $2 \cdot n \ (2 \leq 2 \cdot n \leq 1 \ 000 \ 000)$. The string contains only lowercase letters.

If the string can be restored to a string that satisfies the requirement, output `NO` in the first line. If it cannot be restored, output `YES` in the first line. If a solution exists, output the restored string in the second line. If there are multiple solutions, output any one.

In the first sample, the substrings in the restored string are: `abbab`, `bbabc`, `babcb`, `abcbc`, `bcbcc`, `cbccb`, `bccba`, `ccbab`, `babba`. Note that in the first sample output, there are no repeated substrings, but there are other outputs that also satisfy the requirement. Therefore, the answer is not unique, and the sample only provides one valid output. In the second sample, it is impossible to restore the string to an original string that satisfies the requirement. In the third sample, no operation is needed because the requirement is already satisfied. Translated by ChatGPT 5