P9001 [CEOI 2022] Parking

Valerija works in the parking lot of a restaurant. She is responsible for politely welcoming important guests, keeping their car keys, and helping them park. One evening, she found that there were exactly $2N$ cars in the parking lot she manages. They have $N$ different colors, and each color has exactly two cars. We number the colors from $1$ to $N$. The parking lot has $M$ parking spots, numbered from $1$ to $M$. Each spot can hold two cars and has only one entrance. We call the car closer to the entrance the “top car”, and the one farther from the entrance the “bottom car”. A car can drive out from the entrance if and only if no car blocks it. When parking, Valerija ensures that each spot is either empty, or completely full with two cars, or contains only one bottom car.  This figure shows the first sample and also shows the only first drive. Valerija wants to rearrange the cars so that each pair of cars with the same color ends up in the same parking spot. We do not care which spot corresponds to which color, and we do not care which car is on top and which is on the bottom. Valerija will perform the following operation: - Drive a car that can currently leave its spot, and move it to another spot such that: - the destination spot is empty, and she parks the car in the bottom position, or - the destination spot contains exactly one car, and that car has the same color as the car being driven. Valerija wants to know the minimum number of operations and one optimal sequence of operations. Please solve this problem.

The first line contains two integers $N, M$. The next $M$ lines each contain two integers $b_i, t_i$. Here $b_i$ is the color of the car in the bottom position of this spot, and $t_i$ is the color of the car in the top position of this spot. If a value is $0$, it means there is no car in the bottom/top position.

If it is impossible to meet the requirement, output one line with a single integer $-1$. Otherwise, output a single integer $K$ on the first line, the minimum number of operations. Then output $K$ lines. Each line contains two integers $x_i, y_i$, meaning that in the $i$-th operation, you drive the car that can leave from spot $x_i$ to spot $y_i$. Note that the shortest solution may not be unique. You only need to output any one of them.

### Explanation for Sample 1 From the figure in the statement, we can see that this sample has only one solution. ### Constraints For all testdata, $1 \le N \le M \le 2 \times 10^5$. If your program correctly finds the minimum number of operations but constructs an incorrect sequence, you will get $20\%$ of the score for that test point. | Subtask ID | Special Constraints | Score | | :--------: | :-----------------: | :---: | | $1$ | $M \le 4$ | $10$ | | $2$ | $2N \le M$ | $10$ | | $3$ | $N \le 1000$, each spot is either empty or full. | $25$ | | $4$ | each spot is either empty or full. | $15$ | | $5$ | $N \le 1000$ | $25$ | | $6$ | no special constraints. | $15$ | Translated by ChatGPT 5