import pprint
import itertools
import fileinput

nodes = []
edges = []
for raw in fileinput.input():
	line = raw.strip()
	if line == '': continue
	[a,b] = line.split('-')
	nodes += [a, b]
	edges.append((a, b))

nodes = list(set(nodes))
nodes.sort()

graph = [[0 for j in range(len(nodes))] for i in range(len(nodes))]

#pprint.pprint(graph)

for (a,b) in edges:
	i, j = nodes.index(a), nodes.index(b)
	graph[i][j] = 1
	graph[j][i] = 1

visit_only_once = [e for e in nodes if e.lower() == e and e != 'start' and e != 'end']

start_index = nodes.index('start')
end_index = nodes.index('end')

print(f'{visit_only_once=}')

visit_only_once_index = [nodes.index(e) for e in visit_only_once]

possibles = []

def explore_path(stack, level, locked, s):
	edges = [i for i,e in enumerate(graph[s]) if e]
	
	if s == end_index:
		possibles.append(stack)
		return

	for edge in edges:
		new_locked = locked.copy()
		if edge in locked: continue
		if edge == start_index: continue
		if edge in visit_only_once_index:
			new_locked += [edge]

		#print(f'{level=} , {nodes[edge]=}, {new_locked=}')
		explore_path([s]+stack, level+1, new_locked, edge)

print('start exploring...')

explore_path([], 0, [], start_index)

for p in possibles:
	print([ nodes[i] for i in list(reversed(p))])

print(f'There are {len(possibles)} paths')