# -*- coding: utf-8 -*-
# Auteur : Tessier Josselin
# Rôle : Format du fichier texte
# Date : 22/02/2015
# Version : 1.0.0
from random import randint
##################################################################################
def graph():
	A = { }
	return A
##################################################################################
def graph(nom_fichier):
	fichier = open(nom_fichier, "r")
	D = {}

	for elem in fichier:

		if(not (D.has_key(elem[0]))):
			D[elem[0]] = []

		if(not (D.has_key(elem[2]))):
			D[elem[0]].append(elem[2])
	

		#if(D.has_key(elem[0])):
			#D[elem[0]].append(elem[2])
		#else:
			#D[elem[0]] = elem[2]
			
		
	
	return D
##################################################################################
def nombre_sommets(A):
	nb = len(A)
	
	return nb
##################################################################################
def nombre_aretes(A):
	nb = 0
	for clef, valeur in A.items():
		nb += len(valeur)
		
	return nb	
##################################################################################
def deg(v,A):
	if(A.has_key(v)):
		nb = len(A[v])
		
	else:
		return 0
		
	return nb	
##################################################################################
def present(v,w,A):
	if(A.has_key(v)):
		for clef, valeur in A.items():
			if(clef == v):
				for test in A[clef]:
					if(test == w):
						return 1
		
		return 0		
			
			
	else:
		return 0	
##################################################################################
def insert(i,j,A):
	if(present(i,j,A)):
		return 0	
					
	else:
		if(A.has_key(i)):
			A[i].append(j)
			return 1
			
		else:
			A[i] = [j]

		
##################################################################################
def supp(i,j,A):
	if(present(i,j,A)):
		buffer = A[i]
		buffer.remove(j)
		del A[i]
		A[i] = buffer
		return 1
		
	else:
		return 0
		
##################################################################################
def graph2(n,m):
	i = 0
	D = {}
	for i in xrange(n):
		if(m > 0):
			D[i] = []
			for j in xrange(m):
				x = randint(1,n-1)
				if(not(x in D[i])):
					D[i].append(x)
	return D
##################################################################################
def ParcoursProfondeur(A,s):
	Visites = {}
	print A
	laPile = []
	for i in A:
		Visites[i]= False;

	laPile.append(s)
	while(len(laPile)>0):
		y = laPile.pop()
		if(Visites[y] == False):
			print y
			Visites[y]= True
			for i in A[y]:
				if(Visites[i] == False):
					laPile.append(i)
##################################################################################
def Chaine(A,s,t):
	Visites = {}
	print A
	laPile = []
	PassageDePile = []
	for i in A:
		Visites[i]= False
        laPile.append(s)
        while(len(laPile)>0): 
                y = laPile.pop()
		if(Visites[y] == False):
			PassageDePile.append(y)
			if(y == t):
				return PassageDePile;
			Visites[y]= True
			for i in A[y]:
				if(Visites[i] == False):
					laPile.append(i)

	
	return 0
###################################################################################
def Cycle(A,i,j):
	Visites = {}
	print A
	laPile = []
	PassageDePile = []
	CycleRetour = False
	for i in A:
		Visites[i]= False
	laPile.append(s)
	while(len(laPile) > 0):
            y = laPile.pop()
            if(Visites[y] == False and not(CycleRetour)):
                Visites[y]= True
                PassageDePile.append(y)
                if(y == j):
                    CycleRetour = True
                for elem in A[y]:
                    if(Visites[i] == False):
                        laPile.append(elem)
            elif((Visites[y] == False) and (CycleRetour)):
                PassageDePile.append(y)
                if(y == i):
                    return PassageDePile
	return 0
##################################################################################

A = { 1 : [ 0 , 3 , 4 ], 0 : [ 1 , 2 ], 3 : [ 1 , 2,4], 2 : [ 0 , 3 ], 4 : [ 1,3 ]}

ParcoursProfondeur(A,1)
liste = Chaine(A,0,4)
liste2 = cycle(A,0,4)
print liste
print liste2
raw_input()