ABC165 —— E - Rotation Matching - Problem

You are going to hold a competition of one-to-one game called AtCoder Janken. (Janken is the Japanese name for Rock-paper-scissors.) $N$ players will participate in this competition, and they are given distinct integers from $1$ through $N$. The arena has $M$ playing fields for two players. You need to assign each playing field two distinct integers between $1$ and $N$ (inclusive). You cannot assign the same integer to multiple playing fields. The competition consists of $N$ rounds, each of which proceeds as follows:

For each player, if there is a playing field that is assigned the player's integer, the player goes to that field and fight the other player who comes there.
Then, each player adds $1$ to its integer. If it becomes $N+1$, change it to $1$.

You want to ensure that no player fights the same opponent more than once during the $N$ rounds. Print an assignment of integers to the playing fields satisfying this condition. It can be proved that such an assignment always exists under the constraints given.

Input is given from Standard Input in the following format:
$N\ M$

M

M lines in the format below. The

i

i-th line should contain the two integers

_{i}

ai and

_{i}

bi assigned to the

i

i-th playing field.
$a_1\ b_1$
$a_2\ b_2$
$\dots$
$a_M\ b_M$

$1≤M$
$M×2+1≤N≤200000$

Let us call the four players A, B, C, and D, and assume that they are initially given the integers $1$ , $2$ , $3$ , and $4$ , respectively.

The $1$ -st round is fought by B and C, who has the integers $2$ and $3$ , respectively. After this round, A, B, C, and D have the integers $2$ , $3$ , $4$ , and $1$ , respectively.
The $2$ -nd round is fought by A and B, who has the integers $2$ and $3$ , respectively. After this round, A, B, C, and D have the integers $3$ , $4$ , $1$ , and $2$ , respectively.
The $3$ -rd round is fought by D and A, who has the integers $2$ and $3$ , respectively. After this round, A, B, C, and D have the integers $4$ , $1$ , $2$ , and $3$ , respectively.
The $4$ -th round is fought by C and D, who has the integers $2$ and $3$ , respectively. After this round, A, B, C, and D have the integers $1$ , $2$ , $3$ , and $4$ , respectively.

No player fights the same opponent more than once during the four rounds, so this solution will be accepted.

题目来源：ABC165 E。

5867: ABC165 —— E - Rotation Matching

Description

Input

Output

Constraints

Sample 1 Input

Sample 1 Output

Sample 2 Input

Sample 2 Output

HINT

Source/Category