felinare

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 felinare.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 strazi din Oraşul Trist. Pe fiecare din urmatoarele 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 felinare.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.

Exemplu

felinare.in

4 4
1 2
4 1
4 2
4 3

felinare.out

6
2
3
3
2