British Menu

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.

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.

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