(*

Street Race (IOI 1995)
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




Per trovare i punti inevitabili, scriviamo una funzione ricorsiva che
determina tramite esplorazione in profondita` l'insieme dei nodi raggiungibili
da 0 _senza passare per un nodo dato_. Chiaramente un nodo e` inevitabile
se e solo se N-1 non e` raggiungibile a 0 senza passare per il nodo dato.

Infine, un po' di riflessione conduce alla conclusione che un nodo n e` di
spezzamento se e solo se non esiste un nodo che e` raggiungibile da 0 senza
passare da n, ma che e` raggiungibile da n. Vale quindi la pena di scrivere
una funzione di raggiungibilita` leggermente piu` generale, che permette di
risolvere anche il secondo problema.


*)


Program Race;

CONST
	MAXPUNTI = 50;
	MAXFRECCE = 100;

VAR
	b: array [0..MAXPUNTI-1] of Boolean;	(* Matrice di booleani per
															accumulare il risultato *)
	G: array [0..MAXPUNTI-1, 0..MAXPUNTI-1] of Boolean; (* Matrice di
																			adiacenza del grafo *)
	N: Integer; (* Numero di nodi *)
	i, j, u: Integer;
	t: Boolean;
	F: Text;

(* Questa funzione esplora in profondita` ricorsivamente il grafo,
	marcando i nodi raggiungibili da k senza passare per e (il nodo
	da evitare). Il vettore v contiene un booleano (visitato/non visitato)
	per nodo.

	Si noti che, come accade di frequente, dovendo inizializzare v alla prima
	chiamata conviene dividere in due la funzione--la "vera" funzione
	ricorsiva e` ragg2. Se e e` -1 il calcolo dei nodi raggiungibili viene
	effettuato normalmente (senza ostacoli). *)


VAR v: array [0..MAXPUNTI-1] of Boolean;	(* Nodi visitati *)

PROCEDURE ragg(k, e: Integer);

	PROCEDURE ragg2(k, e: Integer);
	VAR i: Integer;
	BEGIN
		v[k] := TRUE;
		FOR i:=0 TO N-1 DO
			IF (i <> e) AND G[k][i] AND NOT v[i] THEN ragg2(i, e);
	END;

VAR i: Integer;

BEGIN
	FOR i:=0 TO N-1 DO v[i] := FALSE;
	ragg2(k, e);
END;


BEGIN

	ASSIGN(F, '');
	RESET(F);

	N := 0;
	WHILE TRUE DO
	BEGIN
		READ(F, u);
		IF u = -1 THEN BREAK;
		WHILE u <> -2 DO
		BEGIN
			G[N][u] := TRUE;
			READ(F, u)
		END;
		READLN(F);
		N := N+1;
	END;

	N := N+1; (* L'ultimo nodo non compare nella lista di adiacenza. *)

	FOR i:=1 TO N-2 DO
	BEGIN
		ragg(0, i);
		b[i] := NOT v[N-1];
	END;

	ASSIGN(F, '');
	REWRITE(F);

	(* Prima contiamo i nodi j con b[j] vero, e poi stampiamo i loro indici. *)
	j := 0;
	FOR i:=0 TO N-1 DO IF b[i] THEN j := j+1;
	WRITE(F, j);
	FOR i:=0 TO N-1 DO IF b[i] THEN WRITE(F, ' ', i);
	WRITELN(F);

	(* Ora scandiamo i nodi inevitabili, e controlliamo se sono
		di spezzamento. *)

	FOR i:=1 TO N-2 DO
		IF b[i] THEN
			FOR j:=0 TO N-1 DO
			BEGIN
				ragg(0, i);
				t := v[j]; (* = "j e` raggiungibile da 0 senza passare per i". *)
				ragg(i, -1);
				IF t AND v[j] THEN
				BEGIN
					b[i] := FALSE;
					BREAK;
				END;
			END;

	j := 0;
	FOR i:=0 TO N-1 DO IF b[i] THEN j := j+1;
	WRITE(F, j);
	FOR i:=0 TO N-1 DO IF b[i] THEN WRITE(F, ' ', i);
	WRITELN(F);

END.