Fişierul intrare/ieşire:	andrei.in, andrei.out	Sursă	Stelele Informaticii 2010
Autor	Adrian Airinei	Adăugată de	Bogdan-Cristian Tataroiu •bogdan2412
Timp execuţie pe test	0.3 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Andrei

Se da un graf neorientat cu N noduri si M muchii colorate intr-una din culorile: alb, rosu sau violet. Sa se partitioneze multimea nodurilor in doua submultimi A si B astfel incat:

• sa nu existe vreo muchie colorata in alb intre doua noduri din A;
• sa nu existe vreo muchie colorata in rosu intre doua noduri din B;
• sa nu existe vreo muchie colorata in violet intre un nod din A si unul din B.

Date de intrare

Fisierul de intrare andrei.in contine pe prima linie doua numere naturale N si M. Pe fiecare dintre urmatoarele M linii se gasesc trei valori A, B si C. A si B reprezinta doua noduri intre care exista o muchie, iar C culoarea muchiei. C va lua valoarea 0 daca muchia este alba, 1 daca este rosie si 2 daca este violet.

Date de ieşire

In fisierul de iesire andrei.out veti afisa N numere din multimea {0, 1}. Cea de a i-a valoarea va fi 0 daca nodul i face parte din submultimea A, sau 1 daca face parte din B.

Restricţii

• 1 ≤ N ≤ 100000
• 1 ≤ M ≤ 200000
• Se garanteaza ca exista cel putin o solutie.
• Daca exista mai multe solutii puteti afisa oricare dintre ele.
• Intre doua noduri pot exista oricate muchii de orice culoare.

Exemplu

Cum se trimit solutii?