Andrei

andrei

== include(page="template/taskheader" task_id="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$.

Poveste şi cerinţă...

h2. 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.

Fişierul de intrare $andrei.in$ ...

h2. 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$.

În fişierul de ieşire $andrei.out$ ...

h2. 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.

* $... ≤ ... ≤ ...$

h2. Exemplu
table(example). |_. andrei.in |_. andrei.out |

| 4 4
4 3 0
2 4 1
1 2 0
1 3 1
| 0 1 1 0

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|

h3. Explicaţie
 
...
 

== include(page="template/taskfooter" task_id="andrei") ==

4950