Group Excursion

A group of tourists has the chance to visit many beautiful cities. Each member of the group names two cities and, for each of them, says whether they want to visit it or not. A tourist may name the same city twice, wanting to visit it one time and not wanting to visit it the other time.

Write a program that:

• reads the tourists' preferences from standard input,
• decides whether it is possible to build a list of cities to visit (the list may be empty) so that at least one wish of every tourist is fulfilled,
• prints such a list of cities that satisfies all tourists to standard output.

The first line contains two positive integers $n$ and $m$ ($1 \le n \le 20\,000$, $1 \le m \le 8\,000$); $n$ is the number of tourists and $m$ is the number of cities. Tourists are numbered from $1$ to $n$ and cities from $1$ to $m$.

Each of the next $n$ lines contains two nonzero integers separated by a single space. The $i$-th of these lines contains the integers $w_i$ and $w'_i$ describing the wishes of tourist $i$, where $-m \le w_i \le m$, $-m \le w'_i \le m$, $w_i \ne 0$ and $w'_i \ne 0$. A positive number means the tourist wants to visit the city with that number; a negative number means the tourist does not want to visit the city whose number equals its absolute value.

On the first line, print a single non-negative integer $l$, the number of cities to visit. On the second line, print the $l$ city numbers, in increasing order, that must be visited to satisfy all tourists. When $l = 0$, print $0$ on the first line and leave the second line empty.

If no list of cities (possibly empty) can satisfy every tourist, print the word NO on the first and only line.

If several lists of cities satisfy all tourists, print only the lexicographically smallest one. Formally, describe an answer by the binary string $b_1 b_2 \dots b_m$, where $b_j = 1$ if city $j$ is visited and $b_j = 0$ otherwise, and treat $0$ as smaller than $1$. Among all valid answers, choose the one whose string $b_1 b_2 \dots b_m$ is lexicographically smallest (equivalently, scan the cities from $1$ to $m$ and leave each city unvisited whenever the remaining cities can still be chosen so that every tourist is satisfied). Then print the visited cities in increasing order.