/*

Street Race (IOI 1995, semifunzionante)
Copyright (C) 2000 Sebastiano Vigna

This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA




Questa implementazione e` apparentemente "intelligente", ma in realta`
non e` in grado di gestire tutti gli input.

La prima parte del problema consiste nel determinare, dato un
grafo orientato di n nodi, quali sono i nodi del grafo che compaiono su
_tutti_ i cammini da 0 a N-1. Con una scansione in profondita` determiniamo
tutti i cammini semplici (cioe` non autointersecantisi) che vanno da 0 a N-1,
e per ogni cammino eliminiamo da un vettore di booleani i vertici che non vi
compaiono. Si noti che un cammino del genere in un grafo di N nodi non puo`
essere piu` lungo di N nodi.

La seconda parte del problema richiede di determinare i punti di spezzamento
(vedi il testo del problema). In questo caso e` facile vedere che un nodo n
e` di spezzamento se e solo se non esiste un cammino che parte da zero, passa
per n e raggiunge quindi un altro nodo gia` visitato _prima di n_. Una
semplice modifica della routine precedente fornisce quindi il risultato
desiderato.

Il problema di questa soluzione e` che anche a fronte del basso numero
di frecce (100 contro le 2500 teoricamente possibili) il numero di cammini
possibili e` potenzialmente maggiore di 2^50.

*/


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <limits.h>

#define MAXPUNTI 50
#define MAXFRECCE 100

char b[MAXPUNTI]; 	/* Matrice di booleani per accumulare il risultato */
char G[MAXPUNTI][MAXPUNTI]; /* Matrice di adiacenza del grafo */
int N; /* Numero di nodi */

/* Questa funzione esplora in profondita` ricorsivamente il grafo,
	cercando di costruire un cammino da n all'ultimo nodo (N) senza
	passare per i nodi gia` usati e marcati in v. Se arriva in N,
	elimina da b tutti i nodi che non compaiono nel cammino corrente. */

int l; /* Lunghezza attuale del cammino costruito */
int c[MAXPUNTI];	/* Nodi sul cammino corrente */
char v[MAXPUNTI];	/* Marcatura per i nodi sul cammino corrente */

void enumeracammini(int n) {
	int i;

	if (n == N-1) {
		for(i=0; i<N; i++) b[i] &= v[i];
		return;
	}

	for(i=0; i<N; i++)
		if (i != n && G[n][i] && !v[i]) {
      	c[l++] = i;
			v[i] = 1;
			enumeracammini(i);
			v[i] = 0;
			l--;
		}
}


/* Questa funzione e` essenzialemente identica alla precedente, ma tiene
conto nella variabile passato se il punto di spezzamento s e` gia` stato
incontrato o no. I nodi vengono marcati come visitati in v mediante 1 prima
di incontrare s, e mediante 2 dopo. In questo modo possiamo controllare
se raggiungiamo dopo avere visitato s un nodo visitato prima di raggiungere s. */


int s;	/* Punto di spezzamento da controllare */

int spezza(int n, int passato) {
	int i;

	if (n == N-1) return 1;
	if (n == s) passato = 1;

	for(i=0; i<N; i++)
		if (i != n && G[n][i])
			if (v[i]) {
				if (passato && i != s && v[i] == 1) return 0;
			}
			else {
				v[i] = passato ? 2 : 1;
				if (!spezza(i, passato)) {
					v[i] = 0;
					return 0;
				}
				v[i] = 0;
			}

	return 1;
}



int main(int argc, char *argv[]) {

   FILE *f;
	int i, j, u;

	f = stdin;
	for(N=0; ;N++) {
		fscanf(f, "%d", &u);
		if (u == -1) break;
		while(u != -2) {
			G[N][u] = 1;
			fscanf(f, "%d", &u);
		}
		fscanf(f, "\n");
	}
	N++; /* L'ultimo nodo non compare nella lista di adiacenza. */

	/* Inizialmente tutti i nodi, potenzialmente, stanno su tutti
		i cammini, eccetto per 0 e N-1 che non vanno inclusi nell'output. */
	for(i=1; i<N-1; i++) b[i] = 1;
	v[0] = 1;
   l = 0; /* Cominciamo con il cammino vuoto e il primo nodo gia` visitato. */
	enumeracammini(0);

	f = stdout;

	/* Prima contiamo i nodi j con b[j] vero, e poi stampiamo i loro indici. */
	for(i=j=0; i<N; i++) if (b[i]) j++;
	fprintf(f, "%d", j);
	for(i=0; i<N; i++) if (b[i]) fprintf(f, " %d", i);
	fprintf(f, "\n");


	/* I nodi di spezzamento sono necessariamente anche inevitabili, quindi
		ci basta esaminare questi ultimi. */

	v[0] = 1; /* Cominciamo con il primo nodo gia` visitato. */

	for(j=i=0; i<N; i++)
		if (b[i]) {
			s = i;
			b[i] = spezza(0, 0);
			if (b[i]) j++;
		}

	fprintf(f, "%d", j);
	for(i=0; i<N; i++) if (b[i]) fprintf(f, " %d", i);
	fprintf(f, "\n");

	return 0;
}