Rearrangement of Pawns on a Chessboard

You are given an $M \times M$ chessboard and $N$ pawns placed on distinct cells. The task is to rearrange the pawns such that no two pawns share the same row or the same column.

The input provides the grid size and the initial positions of the pawns. A valid configuration must satisfy both:

• $N \le M$ (since there are only $M$ distinct rows and $M$ distinct columns available)
• No two pawns are originally placed in the same row or column.

If these conditions are not met, output Not possible. Otherwise, output the pawn positions in the same order as received.

Note: The problem does not require you to actually rearrange the pawns if the provided configuration is already valid. It only verifies that the given configuration does not violate the constraints.

inputFormat

The first line contains two integers, M and N, where M denotes the size of the grid and N the number of pawns.

The next N lines each contain two integers r and c, representing the row and column of a pawn. Rows and columns are 1-indexed.

outputFormat

If it is possible to have a configuration such that no two pawns are in the same row or the same column, print the N pairs of integers (one pair per line) in the same order as the input.

If such a configuration is not possible, output a single line containing: Not possible.

## sample

5 3
1 1
2 2
3 3

1 1
2 2
3 3

</p>