Camins màxims en un graf P51388

Donat un graf no dirigit sense cicles, calculeu, per a cada vèrtex x, el nombre màxim de passos que es poden fer començant en x sense repetir cap vèrtex.

Entrada

L’entrada consisteix en diversos casos, cadascun amb el nombre de vèrtexs n i el nombre d’arestes m, seguits d’m parells x y indicant una aresta entre x i y, amb x ≠ y. Suposeu 1 ≤ n ≤ 10⁴, 0 ≤ m < n, que els vèrtexs es numeren començant en 0, que no hi ha més d’una aresta entre els mateixos vèrtexs, i que el graf no té cap cicle.

Sortida

Escriviu una línia per a cada cas, amb el nombre màxim de passos que es pot fer començant en 0, començant en 1, …, i començant en n − 1.

Puntuació

• Cas A:  ‍ Casos on n és com a molt 50.  ‍40% Punts ‍

• Cas B:  ‍ Casos de tot tipus.  ‍60% Punts ‍