Regions

Time limit2sMemory limit128 MB

Summary

Given N cities linked by a chain of express roads plus extra directed roads, split cities into equal-size regions that preserve a strict one-way reachability order, maximizing region count.

Level: Medium6 of 10
Topics: Graph, Intervals, Math, Number theory
Solved: No attempts yet

Problem

Bigbang Kingdom has N cities numbered from 1 to N.

There are two kinds of directed roads. First, there are N-1 express roads: for every i (1 ≤ i < N), there is a road from city i to city i+1. In addition, there may be several ordinary roads. Ordinary roads are also directed, and an input pair Si Ei means an ordinary road from city Si to city Ei.

You want to divide all cities into several regions. Every city must belong to exactly one region, and every region must contain the same number of cities. For any two distinct regions A and B, if there is a path from some city in A to some city in B, then there must not be a path from any city in B to any city in A.

Given N, M, and the ordinary roads, find the maximum possible number of regions.

Input

The first line contains the number of cities N and the number of ordinary roads M.

Each of the next M lines contains one ordinary road in the form Si Ei, meaning a directed ordinary road from city Si to city Ei.

The ordinary roads in the input are distinct.

Output

Print the maximum possible number of regions.

Constraints

1 ≤ N ≤ 3,000
1 ≤ M ≤ 1,000
1 ≤ Si, Ei ≤ N
Si ≠ Ei
Ei ≠ Si + 1

Examples4

Example 1
Input
```
6 3
2 1
3 2
6 4
```
Expected output
```
2
```
Example 2
Input
```
3 1
1 3
```
Expected output
```
3
```
Example 3
Input
```
3 1
2 1
```
Expected output
```
1
```
Example 4
Input
```
12 3
3 1
7 6
1 10
```
Expected output
```
3
```