La Conferència de Pau de la Federació (continuació) Y13281

Com ja sabem, en haver resolt el problema Y63099, la Federació de Planetes Units organitza una important conferència de pau on assistiran N delegacions de diferents espècies: Vulcanians, Klingons, Romulans, Bajorans, Ferengis, i altres. Per invitació del seu comandant B. Sisko, la conferència te lloc a l’estació Deep Space 9 en òrbita del planeta Bajor, que aviat s’unirà a la Federació (però no ho ha fet encara). S’ha aconseguit prou progrés i alguns delegats faran una roda de premsa. Triar qui hi participarà és un tema delicat, perquè hi ha delegats que odien altres (moltes vegades, encara que no sempre, l’odi és mutu). No voldríem tenir a la taula de la roda de premsa dos delegats on un odia l’altre, però sí voldríem que hi hagués el màxim possible de delegats.

El doctor Bashir ha vist de seguida totes les possibilitats però, tot seguit, ha marxat a un congrés i no ha deixat cap còpia de les seves anotacions. Et caldrà ajudar a en Sisko tot reconstruint-les. Qapla’!

Entrada

Un enter no negatiu n indicant quants parells de noms segueixen, i n parelles de noms que indiquen que la primera persona de la parella odia a la segona. El valor n apareix sol a una línia i, després, hi ha una parella per línia. Es garanteix que tothom odia algú altre o és odiat per algú altre: no hi ha noms que no apareguin a alguna parella.

Sortida

El número més alt de delegats que poden participar a la roda de premsa sense que ningú dels participants odiï algú altre participant, seguit, a partir de la línia següent, de totes les maneres d’arribar a aquesta grandària, amb una solució per línia.

Pista

Cal aplicar un esquema de backtracking.

Observació

L’enunciat no descarta el valor n = 0. En aquest cas, hi ha exactament una solució (buida!).

Informació sobre el corrector

Podeu escriure en qualsevol ordre tant les solucions com els elements dins de cada solució.