Codeforces Round 899 (Div. 2) |
---|
Finished |
This is the easy version of the problem. The difference between the two versions is that you do not have to minimize the number of operations in this version. You can make hacks only if both versions of the problem are solved.
You have two permutations$$$^{\dagger}$$$ $$$p_{1}, p_{2}, \ldots, p_{n}$$$ (of integers $$$1$$$ to $$$n$$$) and $$$q_{1}, q_{2}, \ldots, q_{m}$$$ (of integers $$$1$$$ to $$$m$$$). Initially $$$p_{i}=a_{i}$$$ for $$$i=1, 2, \ldots, n$$$, and $$$q_{j} = b_{j}$$$ for $$$j = 1, 2, \ldots, m$$$. You can apply the following operation on the permutations several (possibly, zero) times.
In one operation, $$$p$$$ and $$$q$$$ will change according to the following three steps:
Your goal is to simultaneously make $$$p_{i}=i$$$ for $$$i=1, 2, \ldots, n$$$, and $$$q_{j} = j$$$ for $$$j = 1, 2, \ldots, m$$$.
Find any valid way to achieve the goal using at most $$$10\,000$$$ operations, or say that none exists. Please note that you do not have to minimize the number of operations.
It can be proved that if it is possible to achieve the goal, then there exists a way to do so using at most $$$10\,000$$$ operations.
$$$^{\dagger}$$$ A permutation of length $$$k$$$ is an array consisting of $$$k$$$ distinct integers from $$$1$$$ to $$$k$$$ in arbitrary order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ appears twice in the array), and $$$[1,3,4]$$$ is also not a permutation ($$$k=3$$$ but there is $$$4$$$ in the array).
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 2500$$$).
The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$).
The third line contains $$$m$$$ integers $$$b_1, b_2, \ldots, b_m$$$ ($$$1 \le b_i \le m$$$).
It is guaranteed that $$$a$$$ and $$$b$$$ are permutations.
If there is no solution, print a single integer $$$-1$$$.
Otherwise, print an integer $$$k$$$ ($$$0 \le k \le 10\,000$$$) — the number of operations to perform, followed by $$$k$$$ lines, each containing two integers $$$i$$$ and $$$j$$$ ($$$1 \le i \le n$$$, $$$1 \le j \le m$$$) — the integers chosen for the operation.
If there are multiple solutions, print any of them.
Please note that you do not have to minimize the number of operations.
3 5 2 1 3 5 2 1 4 3
2 3 4 2 4
4 4 3 4 2 1 2 4 1 3
5 4 2 3 3 1 4 3 2 4 1
2 2 1 2 2 1
-1
In the first example, we can achieve the goal within $$$2$$$ operations:
In the third example, it is impossible to achieve the goal.
Name |
---|