British Menu

Time limit5sMemory limit1024 MB

Summary

Given a directed graph where every cycle witnesses a repeat within at most four intervening dishes, find the longest simple path (no repeated vertex).

Level: Hard9 of 10
Topics: Graph, Dynamic programming, BFS, Implementation
Solved: No attempts yet

Problem

You have a single free evening in Britain, so you decide to eat as many British dishes as you can in one sitting. The order matters. Blood Pudding directly after Cornish Hevva Cake is not acceptable, but it is fine if you eat Baked Beans in between.

You wrote down every dish, and for each dish you wrote down which dishes may be eaten directly after it. A menu is a sequence of dishes in which every dish except the first may be eaten directly after the dish before it.

The list has one property. Whenever some menu contains the same dish twice, at most four other distinct dishes appear between the two occurrences. A menu like A, B, C, D, E, F, A is therefore impossible, while 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 may exist.

You do not want to eat the same dish twice. Find how many dishes a menu can hold when no dish repeats.

Input

The first line has two integers $n$ and $m$ ( $1 \le n \le 10^5$ , $1 \le m \le 10^6$ ), the number of dishes and the number of compatibilities.

Each of the next $m$ lines has two integers $a$ and $b$ ( $1 \le a \le n$ , $1 \le b \le n$ ), meaning you may eat dish $b$ immediately after dish $a$ .

Dishes are numbered from 1 to $n$ in no particular order. The same pair may appear more than once, and $a$ may equal $b$ . The compatibilities satisfy the property described above.

Output

Print the maximum number of dishes in a menu in which no dish repeats.

Examples2

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