가정이면 충분하다
시간 제한1초메모리 제한1024 MB
두 순열 A와 B가 주어졌을 때, 매 교환이 A의 역전 쌍을 바로잡아 A를 B로 바꾸는 교환 순서를 출력합니다. 그런 순서가 없으면 -1을 출력합니다.
문제
JB는 문제를 풀 때 가정만 있으면 된다고 믿는다. 이를 증명하기 위해 JB는 부터 까지의 수로 이루어진 두 순열 와 를 주었다. JB는 에 대해 다음 조건을 만족하는 원소 교환 연산 의 수열을 원한다.
- 교환하는 두 원소는 그 연산을 수행하는 시점에 역전 쌍을 이루어야 한다. 즉 번째 연산을 수행할 때 이고 이어야 한다.
- 마지막 연산을 마친 뒤 는 가 되어야 한다.
그런 수열이 없으면 불가능하다고 판단한다. 이 문제를 풀어서 JB의 믿음이 맞다는 것을 증명하는 데 도움을 주어라.
입력
첫 줄에 테스트 케이스의 수 가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다.
첫 줄에 와 의 원소 수 ()이 주어진다.
둘째 줄에 서로 다른 정수 ()이 주어진다.
셋째 줄에 서로 다른 정수 ()이 주어진다.
모든 테스트 케이스의 을 합하면 을 넘지 않는다.
출력
각 테스트 케이스에 대해 그런 수열이 없으면 정수 -1 하나를 한 줄에 출력한다.
그렇지 않으면 첫 줄에 연산의 수 ()를 출력한다. 이어서 개의 줄에 각각 번째 연산 를 나타내는 두 정수 와 ()를 출력한다.