La Conferencia de Paz de la Federación (continuación) Y13281

Como ya sabemos, por haber resuelto el problema Y63099, la Federación de Planetas Unidos organiza una importante conferencia de paz a la que asistirán delegaciones de diferentes especies: Vulcanianos, Klingons, Romulanos, Bajoranos, Ferengis, y otros. Por invitación de su comandante B. Sisko, la conferencia tiene lugar en la estación Deep Space 9 en órbita del planeta Bajor, que pronto se unirá a la Federación (pero aún no lo ha hecho). Se han logrado bastantes progresos y algunos delegados darán una rueda de prensa. Elegir a quienes van a participar en ella es un tema delicado, porque hay delegados que odian a otros (muchas veces, aunque no siempre, el odio es mutuo). No queremos tener en la mesa de la rueda de prensa a dos delegados cuando uno de ellos odia al otro, pero sí querríamos que hubiera el máximo posible de delegados.

El doctor Bashir ha visto en seguida todas las posibilidades pero, a continuación, se ha ido a un congreso y no ha dejado ninguna copia de sus anotaciones. Tendrás que ayudar a Sisko reconstruyéndolas. Qapla’!

Entrada

Un entero no negativo n que indica cuántos pares de nombres siguen, y n pares de nombres que indican que la primera persona del par odia a la segunda. El valor n aparece solo en una línea y, después, hay un par por línea. Se garantiza que todo delegado odia a otro o bien es odiado por algún otro: no hay nombres que no aparezcan en algún par.

Salida

El número más alto de delegados que pueden participar en la rueda de prensa sin que ninguno de los participantes odie a ningún otro, seguido, a partir de la línea siguente, de todas las maneras de alcanzar ese tamaño, con una solución por línea.

Pista

Hay que aplicar un esquema de backtracking.

Observación

El enunciado no descarta el valor n = 0. En ese caso, hay exactamente una solución (¡vacía!).

Información sobre el corrector

Podéis escribir en cualquier orden tanto las soluciones como los elementos dentro de cada solución.