JOKER

There are N cards laid out from left to right, and exactly one of them is a joker. The joker is always the rightmost card.

In one move, choose current positions A and B. Neither chosen card may be the joker, and all cards from position A through position B are removed together. Then the cards to the right of the removed block slide left while keeping their order. The move is recorded as (A, B).

After all moves, only the joker should remain on the table. However, the K recorded moves were shuffled into an arbitrary order, and some numbers may also have been changed.

Determine whether the given K records can be executed in some order so that only the joker remains. If possible, output one such order.

The first line contains two integers N and K: the number of cards and the number of moves.

1 <= K < N <= 1,000,000,000

Each of the next K lines contains two integers A and B, describing a recorded move (A, B). It is guaranteed that A <= B.

If a valid execution order exists, output K lines. Each line must contain the A and B of the next move to execute, separated by a space.

If no valid order exists, output -1.