soldati
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
Exemplu
| soldati.in | soldati.out |
|
10 8 1 3 3 4 4 5 3 10 10 8 2 9 10 7 10 6 |
4 |