A venit timpul Anarhiei în Oraşul Trist! Ca revoltă împotriva manifestărilor subculturale, vrei să pui Oraşul pe butuci. În urma unei descinderi ilegale la Primarie, ai „împrumutat” o hartă şi ţi-ai dat seama că există M străzi unidirecţionale între cele N intersecţii ale Oraşului Trist. Fiecare intersecţie are câte două felinare. Primul luminează o jumătate din fiecare stradă care pleacă din intersecţia respectivă, iar al doilea luminează jumătate din fiecare stradă care intră în intersecţie. De exemplu, prima jumătate a străzii dintre intersecţiile A şi B este luminată de primul felinar din intersecţia A, iar cea de-a doua jumătate este luminată de al doilea felinar din intersecţia B. Un felinar stins nu luminează deloc. O stradă este sigură doar atunci când e luminată în totalitate.
Cerinţă
În primul rând, trebuie să te asiguri că nicio stradă nu va fi complet luminată, astfel încât siguranţa cetăţenilor să fie redusă la minim. Dar acest obiectiv nu te mulţumeşte, aşa că în plus îţi doreşti un număr maxim de felinare aprinse, pentru a da o grea lovitură bugetului Primăriei din Oraşul Trist. Odată îndeplinite aceste condiţii, Revoluţia poate începe.
Date de intrare
Fişierul de intrare felinar.in conţine pe prima linie două numere naturale strict pozitive N şi M, reprezentând numărul de intersecţii şi numărul de străzi din Oraşul Trist. Pe fiecare din următoarele linii se află o pereche de numere naturale A şi B cuprinse între 1 şi N reprezentând o stradă care pleacă din intersecţia A şi ajunge în intersecţia B.
Date de ieşire
Fişierul de ieşire felinar.out va conţine pe prima linie un singur număr natural reprezentând numărul maxim de felinare ce pot fi aprinse. Pe următoarele N linii se vor afla numere cuprinse între 0 şi 3, cu semnificaţia următoare: 0 : ambele felinare din intersecţie sunt stinse; 1 : numai primul dintre felinarele din intersecţie este aprins; 2 : numai al doilea dintre felinarele din intersecţie este aprins; 3 : ambele felinare din intersecţie sunt aprinse.
Restricţii
1 ≤ N ≤ 8191
1 ≤ M ≤ 20000
Nu există străzi care să unească o intersecţie cu ea însăşi.
Pentru determinarea numărului maxim de felinare se acordă 40% din punctaj.