결투하는 철학자들

철학자로 가득 찬 방, 스파게티 여러 접시, 그리고 하나 모자란 포크가 얽힌 슬프고 기묘한 사건이 지나간 뒤, ACM 대학교 철학과 교수들은 얼마 전 세상을 떠난 동료의 서류를 정리하고 있다. 그 안에서 출간되지 않은 원고가 잔뜩 나왔다. 교수들은 이 원고를 한 권으로 묶으면 학과에 절실한 좋은 평판을 가져다줄 큰 학술적 성과가 된다고 본다. 그래서 모두가 편집자라는 명예와 명성을 노리고 경쟁하기 시작했다.

긴 논쟁 끝에 후보는 두 사람으로 좁혀졌다. 두 후보 모두 최종 원고를 책 안에 어떤 순서로 배치할지 설명해야 했다. 두 사람은 여러 원고가 다른 원고에서 다루는 용어와 개념을 정의한다는 점을 짚었고, 어떤 용어를 사용하는 원고는 그 용어를 정의한 원고보다 뒤에 와야 한다는 기본 원칙에 함께 동의했다. 한 후보는 그 조건에서 가능한 배치가 오직 하나뿐이라며 자기가 찾은 순서를 내놓았고, 중요한 작업을 이미 끝냈으니 자리를 자기가 받아야 한다고 주장한다. 다른 후보는 그 말을 비웃는다. 가능한 배치가 여럿이며, 그중 가장 좋은 순서를 고르려면 진짜 실력을 갖춘 편집자, 즉 자신이 필요하다고 맞선다.

원고를 배치하는 방법이 하나도 없는지, 정확히 하나인지, 둘 이상인지 판정하는 프로그램을 작성하시오.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에는 정수 $n$과 $m$이 공백 한 개로 구분되어 주어진다 ($1 \le n \le 1000$, $1 \le m \le 500000$). $n$은 원고의 개수이고, $m$은 용어를 공유해서 생기는 원고 사이 관계의 개수이다. 이어지는 $m$개의 줄에는 정수 $d$와 $u$가 공백 한 개로 구분되어 주어진다 ($1 \le d, u \le n$, $d \ne u$). 이는 어떤 용어가 원고 $d$에서 정의되고 원고 $u$에서 쓰인다는 뜻이다. 입력은 0 두 개만 있는 줄로 끝난다.

각 테스트 케이스마다 가능한 배치가 하나도 없으면 0, 정확히 하나이면 1, 둘 이상이면 2를 한 줄에 출력한다. 배치가 몇 가지이든 둘 이상이면 모두 2로 출력한다. 여분의 공백을 출력하지 말고, 답 사이에 빈 줄을 넣지 않는다.