30241번 - 두 순열 (Hard) 스페셜 저지다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 15 | 11 | 11 | 78.571% |
문제
이 버전에서는 시행의 횟수를 최소화해야 한다.
두 순열 $p_{1}, p_{2}, \ldots, p_{n}$과 $q_{1}, q_{2}, \ldots, q_{m}$이 있다. 초기에 $p_{i}=a_{i}$($1 \le i \le n$), $q_{j}=b_{j}$($1 \le j \le m$)이다. 당신은 아래 시행을 적절하게 하여 $p_{i}=i$($1 \le i \le n$), $q_{j} = j$($1 \le j \le m$)가 되도록 해야 한다.
한 번의 시행에서, $p$와 $q$는 다음 세 단계에 따라 변한다:
- 당신은 $1 \le i \le n$, $1 \le j \le m$을 만족하는 두 정수 $i$, $j$를 선택한다.
- $p$에서 $i$번째 원소를 기준으로 왼쪽 부분과 오른쪽 부분을 서로 교환한다. 즉, $p$를 $p_{i+1}, p_{i+2}, \ldots, p_{n}, p_{i}, p_{1}, p_{2}, \ldots, p_{i-1}$로 바꾼다. 왼쪽 부분과 오른쪽 부분은 비어 있을 수도 있다. 새롭게 만들어진 $p$에는 인덱스 번호가 다시 부여된다.
- $q$에서 $j$번째 원소를 기준으로 왼쪽 부분과 오른쪽 부분을 서로 교환한다. 즉, $q$를 $q_{j+1}, q_{j+2}, \ldots, q_{n}, q_{j}, q_{1}, q_{2}, \ldots, q_{j-1}$로 바꾼다. 왼쪽 부분과 오른쪽 부분은 비어 있을 수도 있다. 새롭게 만들어진 $q$에는 인덱스 번호가 다시 부여된다.
목표를 달성하는 것이 가능한지 판별하고, 가능하다면 최소 횟수의 시행으로 목표를 달성하는 방법을 찾아라.
입력
첫 번째 줄에 두 정수 $n$과 $m$이 주어진다($1 \le n, m \le 2500$).
두 번째 줄에 $n$개의 정수 $a_1, a_2, \ldots, a_n$가 공백으로 구분되어 주어진다 ($1 \le a_i \le n$).
세 번째 줄에 $m$개의 정수 $b_1, b_2, \ldots, b_m$가 공백으로 구분되어 주어진다 ($1 \le b_i \le m$).
$a$와 $b$가 순열임이 보장된다.
출력
목표를 달성하는 것이 불가능하다면, 첫 줄에 $-1$을 출력한다.
목표를 달성하는 것이 가능하다면, 첫 줄에 시행의 횟수 $k$를 출력한다.
이후 $k$개의 줄에 각 시행을 나타내는 두 정수 $i$와 $j$를 공백으로 구분하여 출력한다 ($1 \le i \le n$, $1 \le j \le m$).
목표를 달성하는 방법이 둘 이상이라면 그 중 무엇을 출력해도 상관없다. 시행의 횟수를 최소화해야 함에 유의하라.
예제 입력 1
3 5 2 1 3 5 2 1 4 3
예제 출력 1
2 3 4 2 4
예제 입력 2
4 4 3 4 2 1 2 4 1 3
예제 출력 2
3 3 3 1 4 4 2
예제 입력 3
2 2 1 2 2 1
예제 출력 3
-1
노트
첫 번째 예제에서, 다음 방법으로 목표를 달성할 수 있다:
- 첫 번째 시행에서 $i=3$, $j=4$를 선택한다. 시행 후 $p=[3, 2, 1]$, $q=[3, 4, 5, 2, 1]$이 된다.
- 두 번째 시행에서 $i=2$, $j=4$를 선택한다. 시행 후 $p=[1, 2, 3]$, $q=[1, 2, 3, 4, 5]$가 된다.
세 번째 예제에서, 목표를 달성하는 것이 불가능함을 증명할 수 있다.