AT_arc111_c.[ARC111C] Too Heavy

有 $N$ 个人，编号为 $1$ 到 $N$，以及 $N$ 个编号同样为 $1$ 到 $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$ $ \ldots $ $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$ 的一个排列
• 输入的所有数均为整数

样例解释 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$，没有新增疲劳的人。这样所有人都拿到了正确的行李，并且操作次数最少，因此这是一个正确的输出。

样例解释 2

无法通过任何操作满足条件。

样例解释 3

初始状态下已经满足条件。

由 ChatGPT 4.1 翻译