Dueling Philosophers

Time limit2sMemory limit512 MB

Summary

Given directed edges meaning essay d must precede essay u, decide whether the ordering is impossible, unique, or has multiple solutions.

Level: Medium6 of 10
Topics: Graph, Topological sort, Implementation, Queue
Solved: No attempts yet

Problem

After a sad and strange incident involving a room full of philosophers, several plates of spaghetti, and one fork too few, the faculty of the Department of Philosophy at ACM University has been going through the papers of a colleague who died recently. The faculty members were amazed to find a large number of unpublished essays. They believe that the essays, collected into one volume, are a major work of scholarship that will bring the department the positive publicity it badly needs. Every faculty member began to compete for the honor, and the fame, of editing the collection.

After much debate, the list of candidates is down to two. Both applicants were asked to explain how they would arrange the essays inside the final book. Both noted that many essays define terminology and concepts that other essays explore, and both agreed on the basic principle that an essay which uses a term must appear after the essay that defines that term. One candidate has presented what he claims is the only possible arrangement under those constraints, and argues that he should get the job because he has already done this major part of the work. The second candidate scoffs at that claim. He insists that many arrangements are possible, and that picking the best one needs an editor of true skill, meaning himself.

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

Input

The input holds several test cases. Each test case begins with a line containing two integers $n$ and $m$ separated by one space ( $1 \le n \le 1000$ , $1 \le m \le 500000$ ), where $n$ is the number of essays and $m$ is the number of relationships between essays caused by shared terms. Each of the next $m$ lines contains two integers $d$ and $u$ separated by one space ( $1 \le d, u \le n$ , $d \ne u$ ), meaning that some term is defined in essay $d$ and used in essay $u$ . The input ends with a line containing two zeros.

Output

For each test case, print 0 if no arrangement is possible, 1 if exactly one arrangement is possible, or 2 if more than one arrangement is possible. Print 2 however many arrangements there are. Print no extra spaces, and do not separate the answers with blank lines.

Examples6

Example 1

Input

Expected output

2
1
0

Example 2
Input
```
2 1
1 2
0 0
```
Expected output
```
1
```
Example 3
Input
```
2 1
2 1
0 0
```
Expected output
```
1
```
Example 4
Input
```
3 1
1 2
0 0
```
Expected output
```
2
```
Example 5
Input
```
3 2
1 2
1 3
0 0
```
Expected output
```
2
```
Example 6
Input
```
3 3
1 2
2 3
3 1
0 0
```
Expected output
```
0
```