Dueling Philosophers Problem

Following a sad and strange incident involving a room full of philosophers, several plates of spaghetti, and one too few forks, the faculty of the Department of Philosophy at University have been going through the papers of a recently deceased colleague. The faculty members were amazed to find numerous unpublished essays. They believe that the essays, collected into one volume, may constitute a major work of scholarship that will give their department some much-needed positive publicity. Naturally, all of the faculty members began to vie for the honor (to say nothing of the fame) of serving as editor of the collection.

After much debate, the faculty members have narrowed the list to two candidates. Both applicants were asked to explain how they would arrange the essays within the final book. Both have noted that many of the essays define terminology and concepts that are explored in other essays, and both have agreed to the basic principle that an essay that uses a term must itself define that term or appear after the essay that defines it.

One of the candidates has presented what he claims is the only possible arrangement of the essays under those constraints, and is arguing that he should be given the job simply because he has already done this major part of the work. The second candidate scoffs at this claim, insisting that there are many possible arrangements of the essays, and that an editor of true skill (himself) is needed to choose the optimal arrangement.

Write a program to determine if zero, one, or more than one arrangement of the essays is possible.

There will be multiple test cases in the input.

Each test case will begin with a line with two integers, n (1 ≤ n ≤ 1, 000) and m (1 ≤ m ≤ 50, 000), where n is the number of essays, and m is the number of relationships between essays caused by sharing terms.

On each of the next m lines will be two integers, d and u (1 ≤ u,d ≤ n, d ̸= u) which indicate that a term is defined in essay d and used in essay u.

The input will end with two 0s on their own line.

For each test case, print a single line of output containing a 0 if no arrangement is possible, a 1 if exactly one arrangement is possible, or a 2 if multiple arrangements are possible (the output will be “2” no matter how many arrangements there are).