Il boom di mucche congestiona sentieri alla stalla. Farmer John studia strozzature per ridurre «ingorghi» alla mungitura.

$M$ ($1 \le M \le 50,000$) sentieri a senso unico uniscono due diversi tra $N$ ($1 \le N \le 5,000$) incroci $1..N$, stalla in $N$. Vanno a numero maggiore, quindi senza cicli, tutti alla stalla. Più sentieri per coppia possibili.

Nell'ora di punta partono dai propri pascoli alla stalla: esattamente incroci senza sentieri entranti. «Percorso» è sequenza di sentieri da lì alla stalla.

Trova massimo percorsi possibili contenenti un sentiero dato per quello più occupato. Risposta in intero con segno a 32 bit.

Input

Riga 1: interi $N$, $M$ con spazi.

Righe $2..M+1$: due incroci con spazi.

Output

Riga 1: massimo percorsi per sentiero.

Esempi

Input 1

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

Output 1

4

Spiegazione

Quattro percorsi possibili alla stalla:

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

Fonte: USACO marzo 2007.