Forming the Public Peace Committee

According to the constitution, the Public Peace Committee of the Byteland Democratic Republic must be formed through a legislative process in parliament. Unfortunately, due to discord among representatives of some parties, obstacles have arisen. The committee must satisfy the following conditions:

• Each party must have exactly \(1\) representative in the committee.
• If two representatives dislike each other, they cannot both serve on the committee.

In parliament, there are (n) parties and each party has exactly 2 representatives. The representatives are numbered from 1 to (2n). For the (i)-th party, its two representatives are numbered (2i-1) and (2i); note that representative (2i-1) corresponds to the True decision and representative (2i) corresponds to the False decision for that party choice.

A pair of representatives that dislike each other is given. If a representative is chosen for the committee then its corresponding counterpart in their dislike relation must not be chosen. Formally, for a pair of representatives (a) and (b) that dislike each other, it is forbidden that both are selected. This can be written in logical form as: (\lnot(literal_a \land literal_b)), where the literal is interpreted as follows: if (a) is odd then party ((a+1)/2) selects representative (2i-1) (True), otherwise if (a) is even then party (a/2) selects representative (2i) (False).

Your task is to decide whether it is possible to form such a committee. If it is possible, output a valid list of committee members (one representative from each party). If it is impossible to form the committee satisfying all the constraints, output a single line with the string NIE.

inputFormat

The input starts with two integers (n) and (m) where (n) ((1 \leq n \leq 10^5)) is the number of parties and (m) is the number of pairs of representatives who do not get along. Each of the next (m) lines contains two integers (a) and (b) ((1 \leq a, b \leq 2n)) indicating that representative (a) and representative (b) dislike each other.

outputFormat

If a valid committee selection exists, output a line with the string YES followed by a line listing (n) space‐separated integers. The (i)-th integer should be the number of the chosen representative from the (i)-th party. If no valid committee can be formed, output a single line with NIE.

sample

2 1
1 4

YES
2 3