Problem D
British Menu

Hevva Cake by Caitlin on Flickr, cc by

Since you are in Britain, you definitely want to try British food. Unfortunately you will only have a single free evening, so you decided to try all the food you can get in one run. You plan a gigantic meal where you eat one British dish after the other. Clearly not every order of dishes is appropriate. For example, it is not acceptable to eat Blood Pudding directly after Cornish Hevva Cake, but it would be perfectly fine if you chose to eat Baked Beans in between.

You have compiled a comprehensive list of British dishes. For each dish you have also decided which other dishes are fit to be eaten directly afterwards. A menu is a sequence of dishes such that each dish (except the first) is fit to be eaten directly after the previous dish.

After some time studying the list of dishes, you noticed something odd: Whenever it is possible to find a menu in which a dish occurs twice (for example dishes $A$, then $B$, then $C$, then dish $A$ again), there can be at most four different types of dishes between the dish that occurred twice – excluding that dish itself. For example, it is impossible to find a menu like $A, B, C, D, E, F, A$, but it may be possible to find menus like $A, B, C, B, C, B, C, B, C, B, A$ or $A,B,C,D,E,A,B,C,D,E,A$.

But who wants to eat the same dish twice anyway? Clearly, you want to know how many dishes there can be in a menu without repeating any dish!

Input

The input consists of:

• One line with two integers $n,m$ ($1 \leq n \leq 10^5$, $1\leq m \leq 10^6$), the number of dishes and compatibilities.

• $m$ lines, each containing two integers $a$ and $b$ ($1 \leq a,b \leq n$), indicating that you can eat dish $b$ immediately after dish $a$.

Dishes are numbered from $1$ to $n$ in no particular order, and the compatibilities satisfy the constraint described above.

Output

A single integer indicating the maximum number of courses in a menu without repeated dishes.

4 3
1 2
2 3
2 4

3

7 7
1 2
2 3
3 4
4 5
5 2
4 6
5 7

6