Aumento de vacas congestiona trilhas ao celeiro. Farmer John estuda gargalos para reduzir «engarrafamentos» na ordenha.

$M$ ($1 \le M \le 50,000$) trilhas de mão única ligam dois pontos distintos de $N$ ($1 \le N \le 5,000$) interseções $1..N$, celeiro em $N$. Vão a número maior, sem ciclos, todas ao celeiro. Pode haver várias por par.

Na hora de pico saem dos locais de pasto ao celeiro: exatamente pontos sem trilhas entrando. «Caminho» é sequência de trilhas dali ao celeiro.

Ache máximo caminhos possíveis contendo uma trilha dada para achar a mais ocupada. Resposta cabe em inteiro com sinal de 32 bits.

Entrada

Linha 1: inteiros $N$, $M$ com espaços.

Linhas $2..M+1$: dois pontos com espaços.

Saída

Linha 1: máximo caminhos por uma trilha.

Exemplos

Entrada 1

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

Saída 1

4

Nota

Quatro caminhos possíveis ao celeiro:

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

Fonte: USACO março 2007.