Public Order Committee#3127
The Public Order Committee must be legislatively represented in the Parliament of the Democratic Republic of Byteland. Unfortunately, some deputies do not get along with others.
The Committee must satisfy the following conditions:
Each party has exactly one representative in the Committee.
If two deputies do not like each other, they cannot both be members of the Committee.
Each party has exactly two deputies in Parliament. All deputies are numbered from to . Deputies numbered 2i-1 and belong to the -th party.
Write a program which:
reads the number of parties and the number of pairs of deputies who do not like each other,
determines whether it is possible to form the Committee, and if so, outputs the list of its members,
prints the result.
The first line contains two non-negative integers and : the number of parties (1 \leq n \leq 8000) and the number of pairs (0 \leq m \leq 20000) of deputies who do not like each other. Each of the next lines contains two integers and , 1 \leq a < b \leq 2n, separated by a single space. This means deputies and do not like each other.
The input contains multiple test cases. Process input until the end of file.
If it is not possible to form the Committee, print the single word NIE (which means NO in Polish). Otherwise, print integers from to in increasing order, indicating the numbers of deputies forming the Committee. Print each on a separate line. If there are several ways to form the Committee, output the lexicographically smallest sequence.
Example 1