Dueling Philosophers

Following a sad and strange incident involving a room full of philosophers, several plates of spaghetti, and one too few forks, the philosophy department at a university has been going through the papers of a recently deceased colleague. To their amazement, they discovered a large number of unpublished essays. Collected into a single volume, these essays could form a major work of scholarship that would bring the department some much-needed positive attention.

Naturally, every faculty member wants the honor (and fame) of editing the collection. After much debate the field was narrowed to two candidates. Each was asked how they would order the essays in the finished book. Both observed that many essays define terms and concepts that are used by other essays, and both agreed on one basic rule: an essay that uses a term must either define that term itself or appear after the essay that defines it.

The first candidate claims there is only one possible ordering that satisfies this rule, and argues that he deserves the job because he has already done the work. The second candidate scoffs at this, insisting there are many possible orderings and that only a truly skilled editor (himself) can choose the best one.

Write a program that determines whether zero, exactly one, or more than one ordering of the essays is possible.

The input contains multiple test cases.

Each test case begins with a line containing two integers $n$ and $m$ ($1 \le n \le 1000$, $1 \le m \le 50000$), where $n$ is the number of essays and $m$ is the number of ordering relationships between essays caused by shared terms.

Each of the next $m$ lines contains two integers $d$ and $u$ ($1 \le u, d \le n$, $d \ne u$), meaning a term is defined in essay $d$ and used in essay $u$ (so essay $d$ must appear before essay $u$).

The input ends with a line containing two zeros.

For each test case, print a single line containing $0$ if no ordering is possible, $1$ if exactly one ordering is possible, or $2$ if more than one ordering is possible (the output is $2$ no matter how many orderings there are).