만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

가정이면 충분하다

시간 제한1초메모리 제한1024 MB

요약
두 순열 A와 B가 주어졌을 때, 매 교환이 A의 역전 쌍을 바로잡아 A를 B로 바꾸는 교환 순서를 출력합니다. 그런 순서가 없으면 -1을 출력합니다.
난이도

보통10점 중 7점

유형
배열, 정렬, 그리디
정답자
아직 제출이 없습니다

문제

JB는 문제를 풀 때 가정만 있으면 된다고 믿는다. 이를 증명하기 위해 JB는 11부터 nn까지의 수로 이루어진 두 순열 AA와 BB를 주었다. JB는 AA에 대해 다음 조건을 만족하는 원소 교환 연산 (xi,yi)(x_i, y_i)의 수열을 원한다.

  1. 교환하는 두 원소는 그 연산을 수행하는 시점에 역전 쌍을 이루어야 한다. 즉 ii번째 연산을 수행할 때 xi<yix_i < y_i이고 Axi>AyiA_{x_i} > A_{y_i}이어야 한다.
  2. 마지막 연산을 마친 뒤 AA는 BB가 되어야 한다.

그런 수열이 없으면 불가능하다고 판단한다. 이 문제를 풀어서 JB의 믿음이 맞다는 것을 증명하는 데 도움을 주어라.

입력

첫 줄에 테스트 케이스의 수 TT가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다.

첫 줄에 AA와 BB의 원소 수 nn (1≤n≤20211 \le n \le 2021)이 주어진다.

둘째 줄에 서로 다른 정수 A1,A2,…,AnA_1, A_2, \dots, A_n (1≤Ai≤n1 \le A_i \le n)이 주어진다.

셋째 줄에 서로 다른 정수 B1,B2,…,BnB_1, B_2, \dots, B_n (1≤Bi≤n1 \le B_i \le n)이 주어진다.

모든 테스트 케이스의 nn을 합하면 20212021을 넘지 않는다.

출력

각 테스트 케이스에 대해 그런 수열이 없으면 정수 -1 하나를 한 줄에 출력한다.

그렇지 않으면 첫 줄에 연산의 수 kk (0≤k≤n(n−1)20 \le k \le \frac{n(n-1)}{2})를 출력한다. 이어서 kk개의 줄에 각각 ii번째 연산 swap(Axi,Ayi)\text{swap}(A_{x_i}, A_{y_i})를 나타내는 두 정수 xix_i와 yiy_i (1≤xi<yi≤n1 \le x_i < y_i \le n)를 출력한다.

예제1

  1. 예제 1

    입력
    3
    2
    1 2
    2 1
    4
    4 1 2 3
    1 3 2 4
    8
    8 7 6 5 4 3 2 1
    1 8 7 6 5 4 3 2
    
    예상 출력
    -1
    2
    1 2
    2 4
    7
    7 8
    6 7
    5 6
    4 5
    3 4
    2 3
    1 2