Parking Lot Reordering

Valerija works at a restaurant parking lot where she is responsible for receiving important guests, keeping their car keys safe, and helping them park. One evening, she finds that the parking lot contains exactly \(2N\) cars in total with \(N\) different colors; each color appears exactly twice, and the colors are numbered from \(1\) to \(N\).

The parking lot has \(M\) slots numbered from \(1\) to \(M\). Each slot can hold up to two cars. The slot has a single entrance. When two cars occupy the same slot, the car nearer the entrance is called the top car and the one farther from the entrance is the bottom car. A car can leave its slot if and only if there is no car blocking it (i.e. only the top car in a full slot, or the only car in a slot that contains a single car, may exit).

When parking, Valerija ensures that each slot is either empty, filled with two cars, or contains a single car parked in the bottom position. Note that if a slot contains only one car (in the bottom position) it is still accessible (since no car is blocking it).

Her goal is to rearrange the cars such that the two cars of every color end up in the same slot (the order within a slot does not matter). To do so, she is allowed to perform the following operation:

• Drive a car that can exit its current slot and move it to another slot, where:
  - either the destination slot is empty (in which case the moved car will park in the bottom position),
  - or the destination slot contains exactly one car, and that car has the same color as the moved car (in which case the moved car will park on top, forming a pair).

Determine the minimum number of operations required and provide an operation plan (i.e. a sequence of moves) to achieve the goal.

The moves are described by two integers: the source slot number and the destination slot number (both 1-indexed). After a move, the source slot loses its accessible car, and the destination slot either becomes a one-car slot (if it was empty) or a full slot (if it previously contained one car of the same color) with the moved car now on top.

Input is given in the following format:

N M
s1_top s1_bottom
s2_top s2_bottom
...
sM_top sM_bottom

Here, a value of 0 represents an empty position. For a slot with one car (parked in the bottom), the top position is given as 0 and the bottom position is the car's color.

Output format:

K
from_1 to_1
from_2 to_2
...
from_K to_K

Where \(K\) is the number of moves performed and each subsequent line indicates one move.

inputFormat

The first line contains two integers \(N\) and \(M\) (the number of colors and the number of parking slots respectively). The following \(M\) lines each contain two integers describing a parking slot. In each such line, if both numbers are nonzero, the slot is full with the first number representing the top car and the second the bottom car; if the first number is 0 and the second is nonzero, then the slot has only a bottom car; if both are 0, the slot is empty.

It is guaranteed that there are exactly \(2N\) cars in total and that each color \(1, 2, \ldots, N\) appears exactly twice.

outputFormat

Output the minimum number of moves \(K\) on the first line. Each of the following \(K\) lines should contain two integers \(from\) and \(to\), indicating a move from the source slot to the destination slot (both 1-indexed). The provided operation plan must achieve the goal of grouping the two cars of each color into a single slot.

sample

2 3
1 2
0 1
0 2

2
1 2
1 3

</p>