Rezolvare PBinfo #4027

Se dă un graf orientat aciclic (adică nu există circuite). Lungimea unui drum elementar este dată de numărul de arce.

Cerința

Să se determine lungimea maximă a unui drum elementar în acest graf orientat aciclic.

Date de intrare

Programul citește de la tastatură numerele n și m, iar apoi m perechi de noduri i j cu semnificația: există în graf arcul cu extremitatea inițială în nodul i și extremitatea finală în nodul j.

Date de ieșire

Programul va afișa pe ecran un singur număr natural reprezentând lungimea maximă a unui drum elementar.

Restricții și precizări

• 3 ≤ n ≤ 100.000
• 3 ≤ m ≤ 200.000
• Între două noduri va exista cel mult un arc
• Nu există arc de la un nod la el însuși

Exemplu:

Intrare

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

Ieșire

5

Explicație

Cel mai lung drum este 5 4 1 2 6 3, graful din exemplu fiind ilustrat mai jos.