AT_arc111_c [ARC111C] Too Heavy

[problemUrl]: https://atcoder.jp/contests/arc111/tasks/arc111_c $ 1 $ から $ N $ の番号がついた $ N $ 人の人間と、同じく $ 1 $ から $ N $ の番号がついた $ N $ 個の荷物があります。 人 $ i $ の体重は $ a_i $, 荷物 $ j $ の重さは $ b_j $ です。 はじめ人 $ i $ は 荷物 $ p_i $ を持っており、以下の操作を $ 0 $ 回以上繰り返すことで全ての人が自分と同じ番号の荷物を持っている状態にしたいです。 - $ i,j\ (i\ \neq\ j) $ を選び、人 $ i $ と人 $ j $ の荷物を交換する。 ただし、人は自分の体重**以上**の重さの荷物を持つと疲れてしまい、その後一切操作には加われません (すなわち、$ i,j $として選べません)。 特に、 $ a_i\ \leq\ b_{p_i} $ なら一度も操作に加われません。 条件を満たす操作列があるか判定し、存在するならばそのうち**操作回数が最小**であるものをひとつ構成してください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ a_1 $ $ a_2 $ $ \ldots $ $ a_N $ $ b_1 $ $ b_2 $ $ \ldots $ $ b_N $ $ p_1 $ $ p_2 $ $ \ldots $ $ p_N $

どのように操作しても条件を満たせない場合、`-1` を出力せよ。 条件を満たすことが可能な場合、以下のフォーマットで操作列を出力せよ。 > $ K $ $ i_1 $ $ j_1 $ $ i_2 $ $ j_2 $ $ : $ $ i_K $ $ j_K $ ここで $ K $ は操作回数であり、 $ i_t,j_t $ は $ t $ 回目の操作で選んだ人間の番号である。 解が複数存在する場合、どれを出力しても構わない。

### 制約 - $ 1\ \leq\ N\ \leq\ 200000 $ - $ 1\ \leq\ a_i,b_i\ \leq\ 10^9 $ - $ p $ は $ 1,\ \ldots\ ,N $ の順列 - 入力される数はすべて整数 ### Sample Explanation 1 初期状態で人 $ 1,2,3,4 $ が持っている荷物の重さはそれぞれ $ 1,3,3,5 $ なので、初期状態では誰も疲れていません。 まず人 $ 3 $ と $ 4 $ で操作をします。人 $ 1,2,3,4 $ が持っている荷物の重さはそれぞれ $ 1,3,5,3 $ なので、まだ誰も疲れていません。 次に人 $ 1 $ と $ 3 $ で操作をします。人 $ 1,2,3,4 $ が持っている荷物の重さはそれぞれ $ 5,3,1,3 $ なので、人 $ 1 $ が疲れます。 最後に人 $ 4 $ と $ 2 $ で操作をします。人 $ 1,2,3,4 $ が持っている荷物の重さはそれぞれ $ 5,3,1,3 $ なので、これで新たに疲れる人はいません。 これによって全員が正しい荷物を持っている状態になり、さらにこれは最小の操作回数なので、正しい出力の一つです。 ### Sample Explanation 2 条件を満たすように操作することは出来ません。 ### Sample Explanation 3 初期状態で条件を満たしています。