C - Error Swap Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 700 点

問題文

長さ N の整数列 A=(A_1,A_2,\dots,A_N) と B=(B_1,B_2,\dots,B_N) が与えられます。

あなたは以下の操作を 31000 回まで行うことができます。

  • 1 \le i < j \le N を満たす整数の組 (i,j) を選び、A_i を A_j - 1 に、A_j を A_i + 1 に置き換える。

あなたの目標は A=B とすることです。目標が達成可能か判定し、可能な場合はそのような操作列を一つ出力してください。

制約

  • 2 \le N \le 100
  • 1 \le A_i,B_i \le 100

入力

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

N
A_1\ A_2\ \dots\ A_N
B_1\ B_2\ \dots\ B_N

出力

A = B とすることができるならば、Yes を、そうでないならば No を出力せよ。

更に、Yes の場合は以下の形式で操作列を出力せよ。

M
i_1\ j_1
i_2\ j_2
\vdots
i_M\ j_M

M は操作列の長さを表し、0 \le M \le 31000 を満たす必要がある。また、i_k,j_k は k 回目の操作で選ぶ i,j を表し、1 \le i_k < j_k \le N を満たす必要がある。

答えが複数ある場合は、そのどれを出力しても正解になる。

入力例 1

4
2 2 1 4
3 2 2 2

出力例 1

Yes
2
1 4
3 4

以下のように操作をすると A = B とすることができます。

  • (i,j) = (1,4) を選ぶ。A = (3,2,1,3) となる。
  • (i,j) = (3,4) を選ぶ。A = (3,2,2,2) となる。

操作回数を最小化する必要はないため、以下のような出力も正解です。

Yes
6
1 4
3 4
1 2
1 2
1 2
1 2

入力例 2

6
5 4 4 3 4 2
5 1 2 3 4 1

出力例 2

No

入力例 3

7
2 4 2 4 3 2 5
5 4 3 2 5 1 2

出力例 3

Yes
18
5 7
1 7
2 4
1 5
1 5
1 4
4 5
4 5
3 4
5 7
1 5
1 7
1 6
6 7
1 7
2 4
2 5
4 5

Score : 700 points

Problem Statement

You are given two integer sequences of length N: A=(A_1,A_2,\dots,A_N) and B=(B_1,B_2,\dots,B_N).

You may perform at most 31000 operations of the following kind:

  • Choose a pair of integers (i,j) with 1 \le i < j \le N, then replace A_i with A_j - 1 and A_j with A_i + 1.

Your goal is to make A = B. Determine whether the goal is achievable, and if it is, output one sequence of operations that achieves it.

Constraints

  • 2 \le N \le 100
  • 1 \le A_i,B_i \le 100

Input

The input is given from Standard Input in the following format:

N
A_1\ A_2\ \dots\ A_N
B_1\ B_2\ \dots\ B_N

Output

If it is possible to make A = B, output Yes; otherwise, output No.

If you output Yes, also output an operation sequence in the following format:

M
i_1\ j_1
i_2\ j_2
\vdots
i_M\ j_M

M is the length of the operation sequence and must satisfy 0 \le M \le 31000. i_k, j_k are the indices i, j chosen in the k-th operation and must satisfy 1 \le i_k < j_k \le N.

If multiple solutions exist, any of them will be accepted.

Sample Input 1

4
2 2 1 4
3 2 2 2

Sample Output 1

Yes
2
1 4
3 4

The following operations make A = B:

  • Choose (i,j) = (1,4). Then A = (3,2,1,3).
  • Choose (i,j) = (3,4). Then A = (3,2,2,2).

Since minimizing the number of operations is not required, the following output is also accepted:

Yes
6
1 4
3 4
1 2
1 2
1 2
1 2

Sample Input 2

6
5 4 4 3 4 2
5 1 2 3 4 1

Sample Output 2

No

Sample Input 3

7
2 4 2 4 3 2 5
5 4 3 2 5 1 2

Sample Output 3

Yes
18
5 7
1 7
2 4
1 5
1 5
1 4
4 5
4 5
3 4
5 7
1 5
1 7
1 6
6 7
1 7
2 4
2 5
4 5