32995번 - 수열과 수열 스페셜 저지

문제

길이가 $N$인 두 정수 수열 $A\colon A_1, A_2, \cdots, A_N$과 $B\colon B_1, B_2, \cdots, B_N$이 주어진다. 각 수열은 서로 다른 $N$개의 수로 이루어져 있고 1ドル \leq A_i, B_i \leq N$ (1ドル \leq i \leq N$)이다. 이때, 여러분은 $A$에 다음과 같은 연산을 가할 수 있다.

• 1ドル \leq l < r \leq N$이고 $r-l$이 홀수인 양의 정수 $l$과 $r$을 임의로 선택한다.
• $A_l$과 $A_{l+1}$의 값을 바꾼다.
• $A_{l+2}$와 $A_{l+3}$의 값을 바꾼다.
• $\cdots$
• $A_{r-1}$과 $A_r$의 값을 바꾼다.

여러분은 $A$에 연산을 몇 번 가해 $B$와 같아지도록 만들고자 한다. 연산의 횟수를 최소화할 필요는 없으나, 물론 연산을 한 번도 가하지 않을 수도 있다. 이때, $A$에 몇 번의 연산을 통해 $B$와 같도록 할 수 있다면 10ドル^6$번 이하의 연산만으로 $A$를 $B$와 같도록 할 수 있음을 증명할 수 있다. 10ドル^6$번 이하의 연산을 통해 $A$를 $B$와 같도록 만들어보자.

입력

첫 번째 줄에 양의 정수 $N$이 주어진다.

두 번째 줄에 $A$를 이루는 $N$개의 양의 정수 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 주어진다.

세 번째 줄에 $B$를 이루는 $N$개의 양의 정수 $B_1, B_2, \cdots, B_N$이 공백으로 구분되어 주어진다.

출력

첫 번째 줄에 가해야 하는 연산의 횟수 $Q$를 출력하라. 만약 $A$를 $B$로 바꿀 수 없다면 -1을 출력하여라.

만약 $A$를 $B$로 바꿀 수 있다면, 두 번째 줄부터 $Q$개의 줄 중 $i$번째 줄에, 수열 $A$를 $B$로 바꾸는 과정의 $i$번째 연산에서 선택하는 두 수 $l$과 $r$을 공백으로 구분하여 출력하여라.

제한

• 1ドル \leq N \leq 200,000円$

힌트