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 |