12893번 - 적의 적

살면서 너무 많은 적을 만든 용재는 매일 불안에 떨며 지낸다. 언제 들이닥칠지 모르는 적을 대비해 용재는 친구를 만들기로 했다. 하지만 아무것도 없는 관계에서 친구를 만들기는 힘들어서, 용재는 적의 적은 친구 이론을 이용하기로 했다.

적의 적은 친구 이론이란, A와 적대 관계인 B가 있고, B와 적대 관계인 C가 있을 때 A와 C는 우호 관계에 있다는 이론을 말한다. 하지만 이 이론에는 치명적인 단점이 있다. 바로 C와 적대 관계인 D가 있다면, A 역시 D와 적대관계가 되는 것이다. 하지만 또 생각해보면 D와 적대관계인 E가 있다면 E는 A, C와 우호 관계가 된다. 같은 맥락으로, B와 D 역시 우호 관계가 된다.

이 이론에 따라 친구를 사귀게 되면 적도 늘어나겠지만 어쨌거나 용재는 친구가 절실하다. 하지만 아직 이 이론은 전 우주상에서 엄밀히 증명된 적이 없다. 따라서 용재는 이론을 적용하기 전에 먼저 자신의 주위 N명에 관해서 이 이론이 성립하는지를 먼저 검증하고 싶다. 용재를 도와 이 이론이 성립할 수 있는지를 알아보자.

첫 줄에 용재 주위 사람의 수 N(1 ≤ N ≤ 2,000)과 적대관계의 수 M(0 ≤ M ≤ 1,000,000)이 주어진다. 두 번째 줄부터 M개의 줄에 거쳐 서로 적대관계에 있는 사람의 번호 A, B(1 ≤ A, B ≤ N)가 주어진다.

이론이 성립할 수 있다면 1, 그렇지 않다면 0을 출력하라.