평화 위원회

바이트랜드 의회는 평화 위원회를 구성하려고 한다. 정당은 모두 $n$개이며, 각 정당은 정확히 두 명의 의원을 둔다. 의원은 $1$번부터 $2n$번까지 번호가 매겨져 있으며, $i$번째 정당의 두 의원은 $2i-1$번과 $2i$번이다.

위원회는 다음 두 조건을 모두 만족해야 한다.

• 모든 정당에서 정확히 한 명의 의원이 위원회에 들어간다.
• 서로 사이가 나쁜 의원 쌍이 있으며, 사이가 나쁜 두 의원은 동시에 위원회에 들어갈 수 없다.

정당 정보와 사이가 나쁜 의원 쌍이 주어질 때, 위원회를 구성할 수 있는지 판단하고, 가능하다면 그 구성원을 출력하여라.

첫째 줄에 정당의 수 $n$과 사이가 나쁜 쌍의 수 $m$이 공백으로 구분되어 주어진다 ($1 \le n \le 8000$, $0 \le m \le 20000$).

다음 $m$개의 각 줄에는 서로 사이가 나쁜 두 의원의 번호 $a$와 $b$가 주어진다 ($1 \le a < b \le 2n$).

위원회를 구성할 수 없으면 한 줄에 NIE(폴란드어로 ‘아니오’)를 출력한다. 구성할 수 있으면 위원회에 들어갈 의원들의 번호 $n$개를 오름차순으로 한 줄에 하나씩 출력한다. 위원회를 만드는 방법이 여러 가지라면, 사전순으로 가장 앞서는 목록(위에서 아래로 각 줄의 수를 비교했을 때 가장 작은 순서)을 출력한다.