Problem Description

According to the constitution, the Public Peace Committee of the Democratic Republic of Byteland should be established by a legislative procedure in the parliament. Unfortunately, conflicts between representatives of some parties make this difficult. The committee must satisfy the following conditions:

• Each party has exactly $1$ representative in the committee.
• If two representatives hate each other, then they cannot both be in the committee.

Each party has $2$ representatives in the parliament. The representatives are numbered from $1$ to $2n$. Representatives numbered $2i-1$ and $2i$ belong to the $i$-th party.

Task: Write a program that reads the number of parties and the pairs of representatives who are unfriendly to each other, determines whether it is possible to establish the Peace Committee, and if so, outputs the list of its members.

Input Format

The first line contains two non-negative integers $n, m$. They represent the number of parties $n$ and the number of unfriendly representative pairs $m$, respectively.

The next $m$ lines each contain a pair of integers $a, b$, meaning that representatives $a$ and $b$ hate each other.

Output Format

If it is impossible to establish the committee, output NIE.

If it is possible, output $n$ integers chosen from the range $1$ to $2n$, in increasing order, one per line. These numbers are the IDs of the representatives in the committee.

If the committee can be formed in multiple ways, your program may output any one of them.

3 2
1 3
2 4

1
4
5

Hint

For $42\%$ of the testdata, $1 \leq n \leq 100$.

For $70\%$ of the testdata, $1 \leq n \leq 1000$.

For $100\%$ of the testdata, $1 \leq n \leq 8000$, $0 \leq m \leq 20000$, $1 \leq a < b \leq 8000$.

Translated by ChatGPT 5