Description

根据宪法，Byteland民主共和国的公众和平委员会应该在国会中通过立法程序来创立。 不幸的是，由于某些党派代表之间的不和睦而使得这件事存在障碍。 此委员会必须满足下列条件： 每个党派都在委员会中恰有1个代表， 如果2个代表彼此厌恶，则他们不能都属于委员会。 每个党在议会中有2个代表。代表从1编号到2n。 编号为2i-1和2i的代表属于第I个党派。 任务是写一程序： 输入党派的数量和关系不友好的代表对， 计算决定建立和平委员会是否可能，若行，则列出委员会的成员表。

Input Format

第一个行有2非负整数n和m。 他们各自表示：党派的数量n，1＜=n＜=8000和不友好的代表对m，0 ＜=m ＜=20000。 在下面m行的每行为一对整数a,b，1＜=a

Output Format

如果委员会不能创立，输出中应该包括单词NIE。若能够成立，输出中应该包括n个从区间1到2n选出的整数，按升序写出，每行一个，这些数字为委员会中代表的编号。 如果委员会能以多种方法形成，程序输出字典序最小的一个。

Sample

Sample Input

3 2 
1 3 
2 4

Sample Output

1 
4 
5