I - Multiple Swap Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400 点

問題文

長さ N-1 の正整数 A=(A_2,A_3,\ldots,A_N),B=(B_2,B_3,\ldots,B_N) が与えられます。(添字が 2 から始まることに注意してください)

数列 A に対して以下の操作を 10^6 回以下行って A=B にする方法があるか判定し、あるならば 1 つ構築してください。

  • 整数 i\ (2 \le i) とその倍数 j を選び、A_i の値と A_j の値を交換する。なお、このとき i=j であってもよい。

制約

  • 2 \le N \le 50000
  • 1 \le A_i,B_i \le 50000\ (2 \le i \le N)
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N
A_2 A_3 \ldots A_N
B_2 B_3 \ldots B_N

出力

A=B とする方法が存在するならば、以下の形式で出力せよ。

M
I_1 J_1
I_2 J_2
\vdots
I_M J_M

ここで、 M\ (0 \le M \le 10^6) は操作回数を表し、 I_k,J_k は k\ (1 \le k \le M) 回目の操作で選ぶ i,j を表す。

A=B とする方法が存在しないならば、 -1 と出力せよ。

入力例 1

4
3 2 4
4 2 3

出力例 1

1
2 4

入力例 2

2
3
4

出力例 2

-1

入力例 3

6
4 1 3 2 5
1 5 4 2 3

出力例 3

3
3 6
2 4
2 6

原案: turtle0123__