== include(page="template/taskheader" task_id="felinare") ==
Poveste si cerinta...
A venit timpul Anarhiei in Orasul Trist! Ca revolta impotriva manifestarilor subculturale, vrei sa pui Orasul pe butuci. In urma unei descinderi ilegale la Primarie, ai "imprumutat" o harta si ti-ai dat seama ca exista $M$ strazi unidirectionale intre cele $N$ intersectii ale Orasului Trist. Fiecare intersectie are cate doua felinare. Primul lumineaza o jumatate din fiecare strada care pleaca din intersectia respectiva, iar al doilea lumineaza jumatate din fiecare strada care intra in intersectie. De exemplu, prima jumatate a strazii dintre intersectiile $A$ si $B$ este luminata de primul felinar din intersectia {$A$}, iar cea de-a doua jumatate este luminata de al doilea felinar din intersectia {$B$}. Un felinar stins nu lumineaza deloc. O strada este $sigura$ doar atunci cand e luminata {$in totalitate$}.
h2. Cerinta
In primul rand, trebuie sa te asiguri ca nicio strada nu va fi complet luminata, astfel incat siguranta cetatenilor sa fie redusa la minim. Dar acest obiectiv nu te multumeste, asa ca in plus iti doresti un numar maxim de felinare aprinse, pentru a da o grea lovitura bugetului Primariei din Orasul Trist. Odata indeplinite aceste conditii, Revolutia poate incepe.
h2. Date de intrare
...
Fisierul de intrare $felinare.in$ contine pe prima linie doua numere naturale strict pozitive $N$ si {$M$}, reprezentand numarul de intersectii si numarul de strazi din Orasul Trist. Pe fiecare din urmatoarele linii se afla o pereche de numere naturale $A$ si $B$ cuprinse intre $1$ si $N$ reprezentand o strada care pleaca din intersectia $A$ si ajunge in intersectia {$B$}.
h2. Date de iesire
...
Fisierul de iesire $felinare.out$ va contine pe prima linie un singur numar natural reprezentand numarul maxim de felinare ce pot fi aprinse. Pe urmatoarele $N$ linii se vor afla numere cuprinse intre $0$ si {$3$}, cu semnificatia urmatoare:
* $0$ : ambele felinare din intersectie sunt stinse;
* $1$ : numai primul dintre felinarele din intersectie este aprins;
* $2$ : numai al doilea dintre felinarele din intersectie este aprins;
* $3$ : ambele felinare din intersectie sunt aprinse.
h2. Restrictii
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 8191$
* $1 ≤ M ≤ 20 000$
* Nu exista strazi care sa uneasca o intersectie cu ea insasi.
* Pentru determinarea numarului maxim de felinare se acorda $40%$ din punctaj.
h2. Exemplu
table(example). |_. felinare.in |_. felinare.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 4 4
1 2
4 1
4 2
4 3
| 6
2
3
3
2
|
h3. Explicatie
...
== include(page="template/taskfooter" task_id="felinare") ==
== SmfTopic(topic_id="...") ==
