Realitatea TV



Cu mult timp în urmă, într-o galaxie foarte îndepărtată, s-a desfășurat un Consiliu al Cavalerilor Jedi în cadrul căruia s-a discutat problema noii amenințării reprezentate de partea întunecată a Forței. În ultima perioadă au fost semnalate numeroase apariții ale Lorzilor Sith, motiv pentru care Consiliul a trebuit să ia o decizie importantă. După luarea deciziei Yoda a ieșit din Sala de Consiliu și s-a îndreptat direct spre Obi Wan care aștepta cu nerăbdare să afle decizia luată.

Yoda: Consiliul decis este!
Obi Wan: Pari cam nemulțumit, Maestre Yoda.
Yoda: În dezacord cu decizia eu sunt!
Obi Wan: Dar ce s-a hotărât până la urmă?
Yoda: Mulți Cavaleri pe planete îndepărtate trimiși trebuie!
Obi Wan: De ce?
Yoda: Găuri de vierme descoperite au fost! Pentru deplasare rapidă între planete găurile folosite pot fi!
Obi Wan: Și care este problema?
Yoda: Lorzii Sith găuri folosesc pentru scopurile lor mârșave!
Obi Wan: Se cunosc planetele legate prin găuri de vierme?
Yoda: Amplasamentul tuturor intrărilor și ieșirilor găurilor Consiliul îl cunoaște!
Obi Wan: Și ce e de făcut acum?
Yoda: Cavaleri Jedi pe fiecare planetă lângă care se află găuri trimiși vor fi!
Obi Wan: Deci va fi trimis câte un Jedi pe fiecare dintre aceste planete?
Yoda: Mult mai complicată problema este! Numărul Cavalerilor Jedi de pe o planetă diferit să fie trebuie de numărul Cavalerilor de pe oricare planetă legată printr-o gaură de planeta aceea!
Obi Wan: De ce?
Yoda: Forța în acest fel ne-a sfătuit!
Obi Wan: Atunci cred că ar trebui să facem în așa fel încât să trimitem cât mai puțini Jedi!
Yoda: Sfatul tău bun este! Așa vom face!

    Așadar, Consiliul Cavalerilor Jedi va trebui să trimită Cavaleri pe fiecare planetă lângă care a fost descoperită o gaură de vierme, iar numărul Cavalerilor Jedi de pe oricare dintre planete trebuie să fie diferit de cel al Cavalerilor trimiși pe oricare dintre planetele învecinate (legate de planeta respectivă printr-o gaură de vierme). În plus, numărul total al Cavalerilor Jedi trimiși va trebui să fie cât mai mic posibil.

Prima linie a fișierului de intrare STARWARS.IN conține numărul N al planetelor lângă care au fost descoperite găuri de vierme și numărul total M al găurilor descoperite.
    Fiecare dintre următoarele M linii va conține câte două numere x și y, separate printr-un spațiu, cu semnificația: există o gaură de vierme între planeta identificată prin numărul x și planeta identificată prin numărul y.

Fișierul de ieșire STARWARS.OUT va conține N linii. Cea de-a i-a linie va conține numărul Cavalerilor Jedi trimiși pe planeta identificată prin numărul i.

1 <= N <= 100;
1 <= M <= 1000;
planetele sunt identificate prin numere întregi cuprinse între 1 și N;
printr-o gaură de vierme se poate circula în ambele sensuri;
între două planete poate exista cel mult o gaură de vierme;

STARWARS.IN
5 4
1 2
1 3
1 4
1 5

STARWARS.OUT
2
1
1
1
1

Vom considera că pentru fiecare test, se vor putea obține cel mult X puncte.     Concurenții care vor obține cea mai mică valoare NrMin pentru numărul total al Cavalerilor Jedi vor primi X puncte pentru testul respectiv.
    Ceilalți concurenți, care au stabilit o repartizare corectă a Cavalerilor Jedi, dar numărul total al acestora este Nr > NrMin, vor obține X * NrMin / Nr puncte pentru testul respectiv. Această valoare va fi aproximată cu două zecimale exacte.
    Punctajul final va fi obținut prin adunarea punctajelor de la fiecare test și rotunjirea acestuia la cel mai apropiat număr întreg.
    Dacă repartizarea nu respectă condițiile impuse, concurenții nu vor primi nici un punct pentru testul respectiv.
    De exemplu, dacă pentru un test se pot obține cel mult 5 puncte, cel mai bun rezultat obținut de un concurent constă într-o repartizare în care sunt folosiți 24 de Cavaleri Jedi, iar un alt concurent obține o soluție în care este nevoie de 57 de Cavaleri Jedi, atunci, pentru testul respectiv, punctajul concurentului va fi de 5 * 24 / 57 = 2.10 puncte.