Description

Original source: POI 2001

According to the constitution, the Public Peace Committee of the Byteland Democratic Republic should be established through legislative procedures in Congress. Unfortunately, due to discord among certain party representatives, there are obstacles to this matter.

The committee must satisfy the following conditions:

• Each party has exactly $1$ representative in the committee,

• If two representatives dislike each other, they cannot both belong to the committee.

Each party has $2$ representatives in the parliament. 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 pairs of representatives who are unfriendly, determines whether it is possible to establish the Peace Committee, and if so, lists the members of the committee.

Input Format

The first line contains two non-negative integers $n$ and $m$. They represent the number of parties $n$ and the number of unfriendly representative pairs $m$. The next $m$ lines each contain a pair of integers $a, b$, indicating that representatives $a$ and $b$ dislike each other.

Output Format

If the committee cannot be established, output the message NIE. If it can be formed, output $n$ integers selected from the range $1$ to $2n$, one per line, in ascending order. These numbers represent the IDs of the representatives in the committee.

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

Sample 1

3 2
1 3
2 4

1
4
5

Constraints & Hints

$1 \le n \le 8000,0 \le m \le 20000,1 \le a < b \le 2n$