Fişierul intrare/ieşire:andrei.in, andrei.outSursăStelele Informaticii 2010
AutorAdrian AirineiAdăugată debogdan2412Bogdan-Cristian Tataroiu bogdan2412
Timp execuţie pe test0.3 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/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

andrei.inandrei.out
4 4
4 3 0
2 4 1
1 2 0
1 3 1
0 1 1 0
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content