Regions

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.

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.

Print the maximum possible number of regions.

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