Credibility of Witnesses

There are $n$ witnesses, numbered from $1$ to $n$, testifying in court. Each testimony has one of two forms:

• witness $i$ agrees with witness $j$, or
• witness $i$ does not agree with witness $j$.

Agreement carries over other witnesses' opinions. Specifically, if witness $i$ agrees with witness $j$, then:

• witness $i$ agrees with every witness that witness $j$ agrees with, and
• witness $i$ does not agree with every witness that witness $j$ does not agree with.

Every witness always agrees with themselves.

Witness $A$ is not credible if the testimonies together imply that there is some witness $B$ for whom witness $A$ both agrees with $B$ and does not agree with $B$.

Given all testimonies, find every witness who is not credible.

The first line contains an integer $n$ ($1 \le n \le 3000$), the number of witnesses. The second line contains an integer $m$ ($0 \le m \le 8000$), the number of testimonies.

Each of the next $m$ lines contains two integers $i$ and $j$ ($1 \le i \le n$, $1 \le |j| \le n$). If $j$ is positive, the line means "witness $i$ agrees with witness $j$". If $j$ is negative, it means "witness $i$ does not agree with witness $-j$".

Print one of the following:

• the single word NIKT (which means "nobody"), if no witness is not credible, or
• the numbers of all witnesses who are not credible, in increasing order, one per line.