import time
import sys
t1=time.clock()
f=open('in18_7.txt', 'r')
x=f.readline().split()
l=len(x)
arr=[]
for line in f:
       arr.append(list(line.split()))
f.close()
def hamiltonian(g,st,last,hp=[]):
       hp=hp+[st]
       if st==last:
              return [hp]
       if not g.has_key(st):
              return []
       hps=[]
       for node in g[st]:
              if node not in hp:
                     newhps=hamiltonian(g,node,last,hp)
                     for newhp in newhps:
                                   if len(newhp)==len(g):
                                          hps.append(newhp)
                     
       return hps

g={'U': ['V','W','Z'],'V': ['U','X','Y'],'W': ['U','X','Z'],'X': ['W','V','Y'],'Y': ['V','X'],'Z': ['W','U']}
r=hamiltonian(g,x[0],x[l-1])
t2=time.clock()
t=t2-t1
z=str(r)
y=str(t)
ww=sys.getsizeof(t1)+sys.getsizeof(t2)+sys.getsizeof(x)+sys.getsizeof(arr)+sys.getsizeof(g)+sys.getsizeof(l)+sys.getsizeof(z)+sys.getsizeof(t)+sys.getsizeof(y)
memory=str(ww+sys.getsizeof(ww))
out=open("out_17_18_7.txt","w")
out.write(z)
out.write("\nTime taken by program is "+y)
out.write("\nMemory used by program is "+memory+" bytes")
out.close()