import copy

class Nod:
    def __init__(self, nrStare, stare):
        self.nrStare=nrStare
        self.stare=stare

    def totalObiective(self):
        total=0
        for oras in self.stare:
            total+=cautareOrasNumar(oras).obiective
        return total

    def estimareObiective(self):
        estimare=0
        numar=0
        for vecin in cautareOrasNumar(self.stare[-1]).vecini:
            numar+=1
            if vecin not in self.stare:
                estimare+=cautareOrasNumar(vecin).obiective

        if numar>0:
            return estimare/numar
        else:
            return 0

class Oras:
    def __init__(self, numar, obiective, vecini):
        self.numar=numar
        self.obiective=obiective
        self.vecini=vecini

def construireGraf():
    orase=[]
    """ orase.append(Oras(1,0,[2,4,9]))
    orase.append(Oras(2,1,[1,3,9]))
    orase.append(Oras(3,2,[2,4,7]))
    orase.append(Oras(4,6,[1,3,5]))
    orase.append(Oras(5,1,[4,6]))
    orase.append(Oras(6,2,[5,7]))
    orase.append(Oras(7,5,[3,6,8]))
    orase.append(Oras(8,3,[7,9,11]))
    orase.append(Oras(9,4,[1,2,10]))
    orase.append(Oras(10,1,[9,11]))
    orase.append(Oras(11,2,[7,8,10])) """
    orase.append(Oras(1,0,[2,4,9,12,27]))
    orase.append(Oras(2,1,[1,3,9]))
    orase.append(Oras(3,2,[2,4,7]))
    orase.append(Oras(4,6,[1,3,5,27]))
    orase.append(Oras(5,1,[4,6,13,27]))
    orase.append(Oras(6,2,[5,7,15]))
    orase.append(Oras(7,5,[3,6,8,19]))
    orase.append(Oras(8,3,[7,9,11]))
    orase.append(Oras(9,4,[1,2,10,26]))
    orase.append(Oras(10,1,[9,11]))
    orase.append(Oras(11,2,[7,8,10,19,20]))
    orase.append(Oras(12,1,[1,27]))
    orase.append(Oras(13,4,[5,14,15]))
    orase.append(Oras(14,1,[13,16]))
    orase.append(Oras(15,3,[6,13,16]))
    orase.append(Oras(16,2,[14,15,17]))
    orase.append(Oras(17,3,[16,18,19]))
    orase.append(Oras(18,2,[17,19]))
    orase.append(Oras(19,4,[7,11,17,18,20]))
    orase.append(Oras(20,5,[11,19,21,22]))
    orase.append(Oras(21,3,[20,23]))
    orase.append(Oras(22,3,[20,23,24]))
    orase.append(Oras(23,6,[22,24]))
    orase.append(Oras(24,2,[22,23,25]))
    orase.append(Oras(25,1,[24,26]))
    orase.append(Oras(26,4,[9,25]))
    orase.append(Oras(27,2,[1,4,5,12]))
    return orase

def gasitSolutie(nod):
    return (len(nod.stare)>1 and nod.stare[0]==nod.stare[-1]
            and orasObligatoriu in nod.stare and nod.totalObiective()>=minimObiective)

def cautareOrasNumar(numarOras):
    for oras in orase:
        if oras.numar==numarOras:
            return oras

def adaugareFrontiera(nod):
    global frontiera
    # obiectiveNod=nod.totalObiective()
    obiectiveNod=nod.totalObiective()+nod.estimareObiective()

    if len(frontiera)==0:
        frontiera.insert(0,nod)
    else:
        for i in range(0,len(frontiera)):
            # if obiectiveNod>frontiera[i].totalObiective():
            if obiectiveNod>frontiera[i].totalObiective()+frontiera[i].estimareObiective():
                frontiera.insert(i,nod)
                break

def afisareSolutie(nod):
    print(nod.nrStare, nod.stare,nod.totalObiective())


frontiera=[]
teritoriu=[]

orase=construireGraf()
orasObligatoriu=14
minimObiective=30

si=[1]
frontiera.append(Nod(1,si))

while True:
    if len(frontiera)==0:
        print("Insucces")
        break

    nodCurent=frontiera.pop(0)

    if gasitSolutie(nodCurent):
        print("Succes")
        afisareSolutie(nodCurent)
        break

    teritoriu.append(nodCurent)
    orasCurent=cautareOrasNumar(nodCurent.stare[-1])

    for vecin in orasCurent.vecini:
        if vecin not in nodCurent.stare[1:]:
            stareSuccesor=copy.deepcopy(nodCurent.stare)
            stareSuccesor.append(vecin)
            succesor=Nod(len(frontiera)+len(teritoriu)+1,stareSuccesor)
            adaugareFrontiera(succesor)