IPSC 2000




Színes kockák ("H" probléma)
Egy kiváló programozó, Bill Games a Húsvétot nagyszüleinél töltötte. Az öreg házban ráakadt néhány fakockára, egy gyerekjáték alkotóelemeire. Amikor gyerek volt, kastélyt, tornyot, piramist épített ezekből a színes kockákból. Ő megint elkezdett játszani. A probléma, amelynek megoldásával próbálkozott, sokkal bonyolultabb egy egyszerű piramisépítésnél.

A kocka minden oldala színes. Bill tornyot akart építeni az összes kocka felhasználásával. Ez azt jelenti, hogy egyetlen oszlop készül, egyik kocka a másikra kerül. Bill nem akarta a kockákat véletlenszerű sorrendben egymásra helyezni - minden kocka alsó lapjának színe (a legalsót kivéve) meg kell egyezzen az alatta lévő kocka felső lapjának színével.

Bemenet:

A bemeneti állomány első sora két egészet, az M és az N értékét tartalmazza. M a használt színek száma, (a színeket az 1, ... M számok azonosítják), N a kockák száma (a kockákat a bemenet sorrendjében az 1, ... N számok jelölik.)

A következő N sor a kockákat írja le 1, 2, ..., N sorrendben. A kocka leírását 6 egész szám (a színek) jelentik a következő sorrendben: eleje, háta, jobb és bal oldal, alja, teteje.

Kimenet:
Add meg, hogy a bemeneti állományban megadott kockákat hogyan lehet toronnyá rendezni. Minden kockát pontosan egyszer lehet felhasználni. Elég egyetlen megoldást találni. Feltételezzük, hogy létezik megoldás.

A kimeneti állomány N sorból áll. Az i-edik sorban a torony i-edik szintjén levő kocka található. A kocka leírása hét számból áll. Az első a kocka sorszáma (a bemeneti állományban elfoglalt helye alapján), a következő hat szám pedig a lapok színét adja a következő sorrendben: eleje, háta, jobb és bal oldala, alja és teteje. A kockákat természetesen lehet forgatni.

Példa:
 
CUBES.IN CUBES.OUT
6 2
1 2 3 4 5 6
2 1 3 4 5 6
1 6 5 3 4 1 2
2 6 5 3 4 2 1
3 3
1 2 2 2 1 2
3 3 3 3 3 3
3 2 1 1 1 1
1 1 2 2 2 1 2
3 1 1 1 1 2 3
2 3 3 3 3 3 3