적의 적

용재는 살면서 적을 너무 많이 만들어서 매일 불안하게 지낸다. 언제 들이닥칠지 모르는 적에 대비하려고 용재는 친구를 만들기로 했다. 아무 관계도 없는 사람과 친구가 되기는 어려우니, 용재는 적의 적은 친구라는 이론을 쓰기로 했다.

적의 적은 친구 이론은 이렇다. A와 적대 관계인 B가 있고 B와 적대 관계인 C가 있으면 A와 C는 우호 관계다. 이 이론에는 치명적인 단점이 있다. C와 적대 관계인 D가 있으면 A도 D와 적대 관계가 된다. 다시 D와 적대 관계인 E가 있으면 E는 A와 C 모두와 우호 관계가 되고, 같은 맥락에서 B와 D도 우호 관계가 된다.

이 이론을 따라 친구를 사귀면 적도 늘어나겠지만, 어쨌든 용재에게는 친구가 절실하다. 그런데 이 이론은 아직 전 우주에서 엄밀하게 증명된 적이 없다. 그래서 용재는 이론을 적용하기 전에 자기 주위 $N$명에게 이 이론이 모순 없이 성립하는지 먼저 검증하고 싶다. 주어진 적대 관계를 모두 지키면서 $N$명을 두 편으로 나눌 수 있으면 이론이 성립하고, 어떻게 나누어도 같은 편에 적대 관계가 남으면 성립하지 않는다. 용재를 도와 이론이 성립할 수 있는지 알아보자.

첫 줄에 용재 주위 사람의 수 $N$($1 \le N \le 2{,}000$)과 적대 관계의 수 $M$($0 \le M \le 1{,}000{,}000$)이 공백으로 구분되어 주어진다. 이어지는 $M$개의 줄에는 서로 적대 관계인 두 사람의 번호 $A$와 $B$($1 \le A, B \le N$)가 주어진다.

적대 관계에는 방향이 없다. 같은 쌍이 여러 번 주어질 수 있고, $A$와 $B$가 같은 줄도 주어질 수 있다.

이론이 성립할 수 있으면 $1$, 그렇지 않으면 $0$을 한 줄에 출력한다. 자기 자신과 적대 관계인 사람이 있으면 이론은 성립할 수 없다.