#P18208. Closest Derangement
Closest Derangement
Closest Derangement
Blackbird 有一个长度为 的排列 。他想找一个 的错位排列 : 也是长度为 的排列,且对于每个 ,都有 。
同时,他希望
尽可能小。达到这一最小值的排列 称为 的最近错位排列。
最近错位排列可能不唯一。请输出其中字典序第 小的排列;如果最近错位排列不足 个,输出 。
长度为 的排列是由 到 这 个不同正整数组成的序列。对于两个不同的排列 ,在它们第一个不同的位置 上,若 ,则 的字典序小于 。
输入格式
第一行包含一个整数 ,表示测试用例数量。
每个测试用例的第一行包含两个整数 。
第二行包含 个整数 ,表示排列 。
输出格式
对于每个测试用例,若最近错位排列不足 个,输出一行 。
否则,输出一行 个以空格分隔的正整数,表示字典序第 小的最近错位排列 。
数据范围
- ;
- ;
- ;
- 是一个 到 的排列;
- 所有测试用例的 之和不超过 。
样例
输入:
2
2 2
2 1
3 2
1 2 3
输出:
-1
3 1 2
解释:
- 第一个测试用例只有一个最近错位排列 ,所以不存在第 个。
- 第二个测试用例的最近错位排列为 和 。后者的字典序更大,因此是第 小。