raudtee={
  "Tallinn":["Tapa"],
  "Tapa":["Tallinn", "Rakvere", "Tartu"],
  "Rakvere":["Tapa", "Narva"],
  "Narva":["Rakvere"],
  "Tartu":["Tapa", "Petseri", "Valga"],
  "Petseri":["Valga", "Tartu"],
  "Valga":["Tartu", "Petseri"]
}

algkoht="Tallinn"
leitud=[algkoht]
tagasitee={algkoht:algkoht}

while leitud:
  uuritav=leitud.pop(0)
  for koht in raudtee[uuritav]:
     if koht not in tagasitee:
        tagasitee[koht]=uuritav
        leitud.append(koht)
        
print(tagasitee)
sihtkoht="Valga"
teekond=[sihtkoht]
koht=sihtkoht
while not koht==algkoht:
   koht=tagasitee[koht]
   teekond.append(koht)
print("-".join(teekond))
teekond.reverse()
print("-".join(teekond), len(teekond)-1)