Màxima accessibilitat P70158

Donat un graf dirigit, definim l’accessibilitat de cada vèrtex v com el nombre de vèrtexs des dels quals es pot arribar fins a v fent tants passos com calgui. Podeu calcular la màxima de les accessibilitats de tots els vèrtexs d’un graf?

Entrada

L’entrada consisteix en diversos grafs, cadascun amb el nombre de vèrtexs n i el nombre d’arcs m, seguits d’m parells x y indicant un arc des d’x fins a y, amb x ≠ y. Suposeu 1 ≤ n ≤ 10⁴, 0 ≤ m ≤ 10n, que no hi ha cap arc repetit, i que els vèrtexs es numeren entre 0 i n − 1.

Sortida

Per a cada graf, escriviu la màxima accessibilitat dels seus vèrtexs.

Observacions

• Tots els grafs dels jocs de proves privats s’han generat a l’atzar.
• Es poden obtenir 50 punts amb una solució no gaire eficient. Per obtenir els 100 punts cal tractar eficientment grafs amb n gran i amb n ≤ m ≤ 10n.