from math import sqrt, asin

def evklid(s, t):
    if not s or not t:
        return 0
    return sqrt((s[0] - t[0]) ** 2 + evklid(s[1:], t[1:]) ** 2)

def razdalja(kraj1, kraj2):
    return evklid(koordinate[kraj1], koordinate[kraj2])

def naklon(kraj1, kraj2):
    k1, k2 = koordinate[kraj1], koordinate[kraj2]
    return asin((k2[-1] - k1[-1]) / evklid(k1, k2))

def dolzina_poti(pot):
    if len(pot) < 2:
        return 0
    return razdalja(pot[0], pot[1]) + dolzina_poti(pot[1:])

def izbira(kraj1):
    def izbira1(kraji):
        if not kraji:
            return 0, None
        kraj2 = kraji[0]
        nak2 = naklon(kraj1, kraj2)
        ost_nak2, ost_kraj2 = izbira1(kraji[1:])
        if ost_nak2 <= nak2:
            return ost_nak2, ost_kraj2
        else:
            return nak2, kraj2
    return izbira1(list(povezave[kraj1]))[1]

import collections
def dopolni(povezave):
    # to se da rekurzivno (VSE se da rekurzivno - obstajajo jeziki brez zank)
    # vendar je grdo in nesmiselno, saj slovarji in rekurzija ne gredo dobro
    # skupaj. Moral bi definirati dve ali tri dodatne funkcije... Puščam
    # kar nerekurzivno.
    nove = collections.defaultdict(set)
    for kraj1, kraji in povezave.items():
        for kraj2 in kraji:
            nove[kraj1].add(kraj2)
            nove[kraj2].add(kraj1)
    return nove

def pot(kraj):
    if not kraj:
        return []
    return [kraj] + pot(izbira(kraj))

def kam(kraj):
    return pot(kraj)[-1]

def od_kod():
    # Glej komentar pri funkciji 'dopolni'. Tole je sicer narejeno rekurzivno,
    # vendar ni posebej elegantno. Pri 'dopolni' bi bilo še bistveno hujše.
    pov2 = povezave.copy()
    def od_kod1():
        if not pov2:
            return collections.defaultdict(set)
        kraj, sosedi = pov2.popitem()
        od = od_kod1()
        od[kam(kraj)].add(kraj)
        return od
    return od_kod1()

koordinate = {
    "Kranjska Gora": (76, 76, 65.5),
    "Jesenice": (108, 84, 58.0),
    "Radovljica": (122, 115, 49.0),
    "Tržič": (137, 98, 51.0),
    "Kranj": (146, 117, 38.4),
    "Škofja Loka": (138, 130, 36.2),
    "Kamnik": (173, 120, 43.0),
    "Ljubljana": (163, 149, 30.3),
    "Celje": (250, 119, 25.8),
    "Velenje": (231, 96, 40.5),
    "Maribor": (296, 65, 31.0),
    "Ptuj": (321, 88, 24.3),
    "Ljutomer": (359, 72, 26.0),
    "Murska Sobota": (353, 46, 19.6),
    "Lendava": (388, 61, 26.0),
    "Novo mesto": (237, 192, 19.1),
    "Črnomelj": (242, 230, 15.8),
    "Litija": (200, 149, 23.8),
    "Zidani most": (240, 142, 20.7),
    "Krško": (274, 164, 16.4),
    "Ribnica": (186, 202, 49.6),
    "Kočevje": (203, 220, 46.5),
    "Vrhnika": (136, 165, 29.7),
    "Postojna": (127, 158, 55.0),
    "Pivka": (125, 214, 41.1),
    "Sežana": (88, 205, 37.6),
    "Koper": (70, 235, 0.4),
    "Piran": (53, 238, 0.6)
}

povezave = {
    "Kranjska Gora": {"Jesenice"},
    "Radovljica": {"Jesenice", "Tržič", "Kranj"},
    "Kranj": {"Tržič", "Kamnik", "Škofja Loka"},
    "Ljubljana": {"Škofja Loka", "Kamnik", "Litija", "Novo mesto", "Ribnica", "Vrhnika"},
    "Zidani most": {"Litija", "Krško", "Celje"},
    "Celje": {"Zidani most", "Velenje"},
    "Maribor": {"Celje", "Ptuj", "Murska Sobota"},
    "Ljutomer": {"Murska Sobota", "Lendava"},
    "Lendava": {"Maribor"},
    "Črnomelj": {"Novo mesto", "Kočevje"},
    "Kočevje": {"Črnomelj", "Ribnica"},
    "Postojna": {"Pivka", "Sežana", "Koper", "Vrhnika"},
    "Piran": {"Koper"},
    "Koper": {"Piran"},
    "Spodnji Duplek": set()
}

import unittest

class TestGovorice(unittest.TestCase):
    def test_evklid(self):
        self.assertEqual(evklid([10, -4], [13, 0]), 5)
        self.assertEqual(evklid([10, 4], [13, 0]), 5)
        self.assertEqual(evklid([10, -4], [13, -8]), 5)
        self.assertEqual(evklid([10, 4], [13, 8]), 5)

        self.assertEqual(evklid([10], [5]), 5)
        self.assertEqual(evklid([5], [10]), 5)

        self.assertEqual(evklid([1] * 81, [0] * 81), 9)

    def test_razdalja(self):
        self.assertAlmostEqual(razdalja("Celje", "Velenje"), 33.25793138485916)
        self.assertAlmostEqual(razdalja("Velenje", "Celje"), 33.25793138485916)
        self.assertAlmostEqual(razdalja("Maribor", "Koper"), 284.45097995964085)

    def test_naklon(self):
        self.assertAlmostEqual(naklon("Škofja Loka", "Ljubljana"), -0.18572881002345853)
        self.assertAlmostEqual(naklon("Ljubljana", "Škofja Loka"), 0.18572881002345853)
        self.assertAlmostEqual(naklon("Lendava", "Tržič"), 0.09821968572427645)

    def test_dolzina_poti(self):
        self.assertAlmostEqual(dolzina_poti(["Kamnik", "Kranj", "Koper", "Kočevje"]), 314.522540768372)
        self.assertAlmostEqual(dolzina_poti(list(reversed(["Kamnik", "Kranj", "Koper", "Kočevje"]))), 314.522540768372)
        self.assertAlmostEqual(dolzina_poti(["Kamnik", "Kranj"]), 27.55285829092873)
        self.assertAlmostEqual(dolzina_poti(["Kamnik"]), 0)

    def test_izbira(self):
        self.assertEqual(izbira("Ljubljana"), "Litija")
        self.assertEqual(izbira("Kranjska Gora"), "Jesenice")
        self.assertEqual(izbira("Piran"), "Koper")
        self.assertEqual(izbira("Koper"), None)
        self.assertEqual(izbira("Radovljica"), "Kranj")
        self.assertEqual(izbira("Celje"), "Zidani most")
        self.assertEqual(izbira("Lendava"), None)


    def test_dopolni(self):
        pov = dopolni(povezave)
        self.assertEqual(pov["Jesenice"], {"Radovljica", "Kranjska Gora"})
        self.assertEqual(pov["Ljubljana"], {'Škofja Loka', 'Ribnica', 'Kamnik', 'Vrhnika', 'Novo mesto', 'Litija'})
        self.assertEqual(pov["Koper"], {'Piran', "Postojna"})
        self.assertEqual(pov["Piran"], {'Koper'})
        self.assertEqual(pov["Pivka"], {'Postojna'})

    def test_pot(self):
        import copy
        global povezave
        pov_bak = copy.deepcopy(povezave)
        try:
            povezave = dopolni(povezave)
            self.assertEqual(pot("Ljubljana"), ['Ljubljana', 'Litija', 'Zidani most', 'Krško'])
            self.assertEqual(pot("Vrhnika"), ['Vrhnika'])
            self.assertEqual(pot("Postojna"), ['Postojna', 'Vrhnika'])
            self.assertEqual(pot("Maribor"), ['Maribor', 'Ptuj'])
            self.assertEqual(pot("Kranjska Gora"),
                             ['Kranjska Gora', 'Jesenice', 'Radovljica',
                              'Kranj', 'Škofja Loka', 'Ljubljana', 'Litija',
                              'Zidani most', 'Krško'])
            self.assertEqual(pot("Lendava"), ['Lendava'])
        finally:
            povezave = pov_bak

    def test_kam(self):
        import copy
        global povezave
        pov_bak = copy.deepcopy(povezave)
        try:
            povezave = dopolni(povezave)
            self.assertEqual(kam("Ljubljana"), 'Krško')
            self.assertEqual(kam("Vrhnika"), 'Vrhnika')
            self.assertEqual(kam("Postojna"), 'Vrhnika')
            self.assertEqual(kam("Maribor"), 'Ptuj')
            self.assertEqual(kam("Kranjska Gora"), 'Krško')
            self.assertEqual(kam("Lendava"), "Lendava")
        finally:
            povezave = pov_bak

    def test_od_kod(self):
        import copy
        global povezave
        pov_bak = copy.deepcopy(povezave)
        try:
            povezave = dopolni(povezave)
            t = od_kod()
            if "Spodnji Duplek" in t:
                del t["Spodnji Duplek"]
            print(t)
            self.assertEqual(
               t,
               {'Krško': {'Radovljica', 'Litija', 'Tržič', 'Celje', 'Velenje',
                          'Zidani most', 'Kranj', 'Krško', 'Kamnik', 'Jesenice',
                          'Ljubljana', 'Ribnica', 'Kranjska Gora',
                          'Škofja Loka'},
                'Sežana': {'Sežana'}, 'Koper': {'Koper', 'Piran'},
                'Vrhnika': {'Postojna', 'Vrhnika'},
                'Murska Sobota': {'Murska Sobota', 'Ljutomer'},
                'Črnomelj': {'Novo mesto', 'Kočevje', 'Črnomelj'},
                'Lendava': {'Lendava'}, 'Pivka': {'Pivka'},
                'Ptuj': {'Maribor', 'Ptuj'}})
        finally:
            povezave = pov_bak