Gráfok színezése (2 színnel optimális színezés)

Írjunk programot, amely megkeresi egy adott gráf optimális színezését! Gráf színezése alatt a csúcsok fekete vagy fehér színnel való színezését értjük. A színezést optimálisnak nevezzük, ha a fekete csúcsok száma maximális. A színezéseket megszorítjuk azzal a feltétellel, hogy fekete csúcsok nem lehetnek szomszédosak. Az ábrán a példában szereplő gráf egy optimális színezése látható három fekete csúccsal.

Bemenet:

A gráf csúcsait az (n<=100) számokkal, éleit (n₁, n₂) párokkal (n₁<>n₂) adjuk meg. Az input fájl m gráf leírását tartalmazza. Az input első sora tartalmazza az m számot. Minden gráf leírásának első sora az n és k egészekből áll; n a gráf csúcsainak, k az éleinek a száma. Az ezt követő k sor mindegyike a gráf egy élét írja le, az él végpontjainak azonosítói által.

Kimenet:

Az output minden gráfhoz két sort, összesen 2m sort tartalmaz. Az első sor a gráfban feketére színezhető csúcsok maximális számát tartalmazza. A második sor egy optimális színezésben a fekete csúcsok azonosítóiból áll.

Példa:

INPUT.TXT

OUTPUT.TXT

1
6 8
1 2
1 3
2 4
2 5
3 4
3 6
4 6
5 6

1 4 5

(ACM regionális verseny 1995)