class Zahradka:
    #{vrchol1:{sused1: ovocie, sused2:ovocie}, vrchol2:...}

    def __init__(self, meno_suboru):
        self.g = {}
        self.vsetko_ovocie = set()

        with open(meno_suboru, 'r') as subor:
            for riadok in subor:
                riadok = riadok.strip().split()

                if len(riadok) == 2:
                    v1 = riadok[0]
                    ovocie = ''
                    v2 = riadok[1]
                else:
                    v1 = riadok[0]
                    ovocie = riadok[1]
                    self.vsetko_ovocie.add(ovocie)
                    v2 = riadok[2]

                self.g.setdefault(v1, {})[v2] = ovocie #ak v1 este nie je v self.g, nastavim mu hodnotu {} a potom pridam v2
                self.g.setdefault(v2, {})[v1] = ovocie

        #print(self.g)

    def vrcholy(self):
        return set(self.g.keys())              # vrati mnozinu alebo postupnost vrcholov

    def hrana(self, v1, v2):   # vrati retazec alebo None
        if v2 not in self.g[v1]:
            return None
        return self.g[v1][v2]


    def typy_ovocia(self):
        return self.vsetko_ovocie            # vrati mnozinu alebo postupnost mien ovocia

    def start(self, v1):
        self.vysledok = []
        self.visited = set() #obsahuje hrany - n-tice
        self.hodnoty = set() #obsahuje "navstivene" ovocie
        self.backtracking(v1, [v1])

        return self.vysledok              # vrati postupnost vrcholov cesty alebo []

    def backtracking(self, vrchol, cesta): #do cesty budem pridavat vrcholy
        if len(self.hodnoty) == len(self.vsetko_ovocie): #skoncim ked pozbieram vsetko ovocie
            self.vysledok = cesta[:]
            return

        for sused in self.g[vrchol]:
            hodnota_hrany = self.g[vrchol][sused]

            if (vrchol, sused) not in self.visited and hodnota_hrany not in self.hodnoty:
                self.visited.add((vrchol, sused))
                self.visited.add((sused, vrchol))

                if hodnota_hrany != '':
                    self.hodnoty.add(hodnota_hrany)
                #print(hodnota_hrany)
                self.backtracking(sused, cesta+[sused])

                self.visited.remove((vrchol, sused))
                self.visited.remove((sused, vrchol))
                if hodnota_hrany != '':
                    self.hodnoty.remove(hodnota_hrany)