Рост числа коров создаёт заторы на дорогах к сараю. Farmer John изучает узкие места для снятия «пробок» при доении.

$M$ ($1 \le M \le 50,000$) односторонних троп соединяют разные пары $N$ ($1 \le N \le 5,000$) перекрёстков $1..N$; сарай в $N$. Каждая идёт к большему номеру, значит циклов нет и все ведут в сарай. Пара точек может иметь несколько троп.

В час пик коровы идут из своих пастбищных точек к сараю. Это ровно точки без входящих троп. «Путь» — последовательность троп от такой точки до сарая.

Найдите максимум возможных путей через какую-либо одну тропу для определения самой загруженной. Ответ в знаковом 32-битном целом.

Входные данные

Строка 1: целые $N$, $M$ через пробел.

Строки $2..M+1$: две точки через пробел.

Выходные данные

Строка 1: максимум путей через одну тропу.

Примеры

Входные данные 1

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

Выходные данные 1

4

Примечание

Четыре возможных пути к сараю:

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

Источник: USACO, март 2007.