Problem Description

Valerija works at a restaurant's parking lot, where she courteously greets important guests, holds their car keys, and assists them with parking.

One evening, she discovers that there are exactly $2N$ cars in the parking lot she manages, with $N$ different colors, each color having exactly two cars. The colors are numbered from $1$ to $N$.

The parking lot has $M$ spaces, numbered from $1$ to $M$, each capable of holding two cars. Each space has only one entrance, with the car closer to the entrance being the "top car" and the one farther away being the "bottom car". A car can exit the space if and only if no other car is blocking it. Valerija ensures that each space is either empty, full, or contains only a bottom car.

This diagram illustrates the first sample case and shows the only initial move.

Valerija wants to rearrange the cars so that each pair of cars of the same color is in the same space. It does not matter which space corresponds to which color or which car is on top or bottom. Valerija will perform the following operations:

• Drive a car that can exit its space to another space, satisfying:
• The space is empty and the car is parked at the bottom, or
• The space contains exactly one car of the same color.

Valerija wants to know the minimum number of operations and the sequence of operations to achieve this. Please solve this problem.

Input Format

The first line contains two integers $N$ and $M$.

The next $M$ lines each contain two integers $b_i$ and $t_i$, where $b_i$ represents the color of the car at the bottom of the space, and $t_i$ represents the color of the car at the top of the space. If it is $0$, it means there is no car in the bottom/top position.

Output Format

If it is not possible to achieve the requirement, output a single integer $-1$.

Otherwise, the first line should contain an integer $K$, the minimum number of operations.

The next $K$ lines should each contain two integers $x_i$ and $y_i$, indicating that the car in space $x_i$ that can exit is driven to space $y_i$ during the $i$-th operation.

Note that there may be multiple shortest solutions; you only need to output any one of them.

Sample Input and Output

Sample Input #1

4 5
1 0
2 0
1 3
4 4
3 2

Sample Output #1

3
5 2
3 5
3 1

Sample Input #2

4 5
0 0
2 1
3 1
3 4
2 4

Sample Output #2

-1

Sample Input #3

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

Sample Output #3

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

Notes/Hints

Sample 1 Explanation

As shown in the problem description's diagram, this sample has only one solution.

Data Constraints

For all data, $1 \le N \le M \le 2 \times 10^5$.

If your program correctly calculates the minimum number of operations but the solution construction is incorrect, you will receive $20\%$ of the points for that case.

见题面 Input 部分

见题面 Output 部分