linnad={}
tagasiTeed={}
tulbalaius=8

def loeLinnad():
 for rida in open("teed1.txt", "r"):
  m=rida.strip().split()
  linnad[m[0]]=m[1:]
  
def leiaJ2rgmineJaam(sihtlinn, alglinn):
    if(sihtlinn in tagasiTeed and alglinn in tagasiTeed[sihtlinn]):
      return (tagasiTeed[sihtlinn][alglinn]).ljust(tulbalaius)
    else:
      return "-".ljust(tulbalaius)
      
#Lisage väljatrükiks teine funktsioon, kus kriipsud on 
#asendatud k või x-iga vastavalt sellele, kas juba kohal
#Katsetage mõlemat väljatrükki

def leiaJ2rgmineJaamVoiKohal(sihtlinn, alglinn):
    if(sihtlinn in tagasiTeed and alglinn in tagasiTeed[sihtlinn]):
      return (tagasiTeed[sihtlinn][alglinn]).ljust(tulbalaius)
    if sihtlinn==alglinn: return "k".ljust(tulbalaius)
    return "x".ljust(tulbalaius)
   

def trykiTabel(tegevus):
 for veerulinn in ["algus"]+list(linnad.keys()):
  print(veerulinn.ljust(tulbalaius), end="")
 print()  
 for realinn in linnad:
  print(realinn.ljust(tulbalaius), end="")
  for veerulinn in linnad:
    print(tegevus(realinn, veerulinn), end="")
  print()
  
def leiaTagasitee(kuhu):
  leitudLinnad=[kuhu]
  uuritudLinnad=[]
  tagasiTee={}
  while leitudLinnad:
    uuritav=leitudLinnad.pop()
    for uusLeitud in linnad[uuritav]:
      if uusLeitud not in (leitudLinnad+uuritudLinnad):
       leitudLinnad.append(uusLeitud)
       tagasiTee[uusLeitud]=uuritav
    uuritudLinnad.append(uuritav)
  return tagasiTee
  
def leiaTagasiteed():
  for linn in linnad:
    tagasiTeed[linn]=leiaTagasitee(linn)

loeLinnad()
leiaTagasiteed()
trykiTabel(leiaJ2rgmineJaam)
print()
tulbalaius=12
trykiTabel(leiaJ2rgmineJaamVoiKohal)