Informatika gyűjtemény

Egy szinttel feljebb Csoport beosztás_2011

2004050607080910

NézetNyomtat

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 kedveli 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

csoport.becsoport.ki
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