In
perioada urmatoare toti cei N
soldati din unitatea UM 07451 trebuie sa fie scosi la instructie. Pentru a evita
orice conflict posibil, comandatul unitatii a cerut serviciului de informatii
date despre conflictele care au avut loc intre soldati. Serviciul de informatii
a exprimat relatiile conflictuale dintre soldati sub forma a M
perechi ordonate (a, b),
cu semnificatia ca soldatii a
si b au avut un conflict fizic
in trecut, iar soldatul a a avut
castig de cauza.
Intre soldatii scosi la instructie in aceeasi zi nu se pot gasi 2 soldati a
si b pentru care sa mai existe
alti k (k>=0)
soldati x1, x2,
... xk astfel incat
sa avem relatiile (a, x1),
(x1, x2),
... , (xk-1, xk),
(xk, b),
deoarece asta ar insemna ca soldatul a
este violent si se poate sti cu siguranta ca il va bate pe soldatul b.
Cerinta Scrieti un program
care sa determine numarul minim de zile necesare pentru a scoate toti ce N
soldati la instructie.
Date de intrare Pe prima linie
a fisierului de intrare soldati.in
sunt scrise numerele N si M.
Pe urmatoarele linii apar cele M
perechi de soldati.
Date de iesire Prima linie a
fisierului soldati.out va contine
numarul minim de zile in care toti soldatii pot fi scosi la instructie.
Restrictii
1 <= N <= 16383
0 <= M <= 131072
0 <= k <= N-2
Exemplu
soldati.in
soldati.out
10 8
1 3
3 4
4 5
3 10
10 8
2 9
10 7
10 6
4
Tiberiu-Lucian Florea
Universitatea Bucuresti
Contact: tiberiu.florea
[at] gmail [dot] com