Height Order

Interview

Time limit1sMemory limit128 MB

Summary

Given pairwise shorter-than relations between students, count how many students have their exact height rank fully determined by transitivity.

Level: Medium5 of 10
Topics: Graph, DFS, Bit manipulation
Solved: No attempts yet

Problem

There are N students numbered from 1 to N. Every student has a different height, and only some pairs of students have been compared.

The comparison results are transitive. If one student is shorter than a second student, and the second student is shorter than a third student, then the first student is also shorter than the third student.

A student's exact rank by height is known if, for every other student, it can be determined whether that other student is shorter or taller. Given the comparison results, compute how many students can determine their exact height rank.

Input

The first line contains the number of students N (2 ≤ N ≤ 500) and the number of height comparisons M (0 ≤ M ≤ N(N-1)/2).

Each of the next M lines contains two distinct student numbers a and b, both between 1 and N. This means student a is shorter than student b.

Output

Print the number of students whose exact height rank can be determined from the given comparisons.

Examples3

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