결투하는 두 철학자

한 방 가득한 철학자들, 여러 접시의 스파게티, 그리고 하나 모자란 포크가 얽힌 슬프고 기묘한 사건이 있은 뒤, 한 대학의 철학과 교수진은 최근 세상을 떠난 동료의 유고를 정리하고 있었다. 그러던 중 아직 발표되지 않은 수많은 에세이를 발견하고 크게 놀랐다. 이 에세이들을 한 권으로 묶으면 학과에 꼭 필요한 좋은 평판을 가져다줄 만한 중요한 학문적 저작이 될 수 있었다.

당연하게도 모든 교수가 이 선집의 편집자라는 영예(그리고 명성)를 얻고자 경쟁하기 시작했다. 오랜 논쟁 끝에 후보는 두 명으로 좁혀졌다. 두 후보는 각각 최종 책에서 에세이를 어떤 순서로 배열할지 설명해야 했다. 두 사람 모두 많은 에세이가 다른 에세이에서 사용되는 용어와 개념을 정의한다는 점에 주목했고, 한 가지 기본 원칙에 동의했다. 어떤 용어를 사용하는 에세이는 그 용어를 스스로 정의하거나, 그 용어를 정의한 에세이보다 뒤에 놓여야 한다는 것이다.

첫 번째 후보는 이 규칙을 만족하는 배열이 오직 하나뿐이라고 주장하며, 이미 그 작업을 끝냈으니 자신이 편집을 맡아야 한다고 말한다. 두 번째 후보는 이를 비웃으며, 가능한 배열이 여러 개이고 그중 최적의 배열을 고르려면 진정으로 뛰어난 편집자(바로 자신)가 필요하다고 반박한다.

가능한 에세이 배열이 0개인지, 정확히 1개인지, 아니면 2개 이상인지 판정하는 프로그램을 작성하라.

입력은 여러 개의 테스트 케이스로 이루어진다.

각 테스트 케이스는 두 정수 $n$과 $m$ ($1 \le n \le 1000$, $1 \le m \le 50000$)이 주어지는 줄로 시작한다. 여기서 $n$은 에세이의 수, $m$은 용어 공유로 인해 생기는 에세이 사이의 순서 관계의 수이다.

이어지는 $m$개의 줄에는 각각 두 정수 $d$와 $u$ ($1 \le u, d \le n$, $d \ne u$)가 주어진다. 이는 어떤 용어가 에세이 $d$에서 정의되고 에세이 $u$에서 사용됨을 뜻한다(즉, 에세이 $d$는 에세이 $u$보다 앞에 놓여야 한다).

입력의 끝은 두 개의 0이 적힌 줄로 표시된다.

각 테스트 케이스마다 한 줄을 출력한다. 가능한 배열이 없으면 $0$, 정확히 하나이면 $1$, 두 개 이상이면 $2$를 출력한다(배열이 몇 개든 상관없이 두 개 이상이면 $2$를 출력한다).