#P18055. Organize the Bookshelf
Organize the Bookshelf
Organize the Bookshelf
给定两个长度为 的整数序列 。你可以执行以下操作:选择 ,交换 和 ,代价为 。
请使两个序列对应位置的数全部相等,并使总代价最小。输出的操作次数不能超过 ;可以证明,只要有解,就存在不超过 次操作的最优方案。
输入格式
第一行一个整数 ,。每个用例包含:
- 一行一个整数 ,。
- 一行 个整数 。
- 一行 个整数 。
所有 均在 内。所有用例的 之和不超过 。
输出格式
若无解,输出一行 。
否则第一行输出两个整数 cost num,分别是最小总代价和操作次数,要求 。随后输出 num 行,每行两个整数 ,表示交换当前的 。
允许输出任意最优方案。注意 的交换是合法的,代价为 。
样例
输入:
3
3
1 1 3
3 2 2
4
1 2 2 3
4 4 3 1
2
1 1
2 1
输出(一种合法答案):
2 2
2 1
3 2
3 4
1 2
3 2
4 4
4 3
-1