teed={}
for rida in open("linnad1.txt", "r"):
  m=rida.strip().split()
  teed[m[0]]=m[1:]
  
sihtlinn="Haapsalu"
leitud=[sihtlinn]
uuritud=[]
tagasitee={}

while leitud:
  uuritav=leitud.pop() #Massiivist esimene element
  for koht in teed[uuritav]:
   if koht not in leitud+uuritud:
     leitud.append(koht)
     tagasitee[koht]=uuritav
  uuritud.append(uuritav)

#print(leitud)
#print(tagasitee)
print("Sihtlinn: ", sihtlinn)
for koht in tagasitee:
 print(koht, '->', tagasitee[koht])
 
koht="Rapla"
teekond=[]
while koht in tagasitee:
  teekond.append(koht)
  koht=tagasitee[koht]
teekond.append(sihtlinn)
  
print( " - ".join(teekond))