Programozás‎ > ‎Feladatok‎ > ‎

Csoport beosztás

Egy kiránduláson részvevő tanulókból két csapatot kell csinálni. A két csapatot úgy kell képezni, hogy ha X és Y barátok, akkor azonos csoportba kerüljenek, de ha nem kedvelik egymást, akkor nem kerülhetnek egy csoportba. 

Feladat

Készíts programot, ami kiszámít egy, a feltételeknek megfelelő csoportbeosztást.

Bemenet

Az első sorban a tanulók N száma, a baráti párok M száma és az "ellenséges" párok K száma van. (N 1 és 500 közötti, M és K 1 és 20000 közötti.) Ezután M sorban a baráti párok, majd K sorban az ellenséges párok következnek. 

Kimenet

Két sorból áll, ahol a csoportok tagjainak sorszámát adjuk meg. Ha nincs megoldás, akkor egyetlen -1-et kell kiírni. 

Példa

Bemenet  Kimenet
11 7 4
1 2
3 4
5 6
9 10
10 11
11 9
7 8
2 3
6 9
8 4
7 11
1 2 5 6 7 8
3 4 9 10 11

Tesztadatok

Címkék

A feladat forrása: NTOITV 2011, 11-13. évfolyam, 3. forduló
Algoritmusok:

megoldás