#RM4MP Rahat Maini HW7
import itertools

with open("chapel.txt", 'r') as inputFile:
    lines=inputFile.read()
inputFile.close()
lines=lines.split("\n")

with open("chapel.txt", 'r') as inputFile2:
    lines2=inputFile2.read()
inputFile2.close()
lines2=lines2.split()




#lines[0] is number of rooms/vertices
#lines[1] is start end for luke
#lines[2] is start end for lorelai
#rest of lines are adjacencies to their index (basically n-3 is room number)

adjacencies=[]
graph={}
i=3

while (i<len(lines)):
    adjacencies.append(lines[i].split(" "))
    adjacencies[i-3].append(str(i-3))
    graph[str(i-3)]=adjacencies[i-3]
    i+=1


tuplList=[]

x=0
while (x<len(adjacencies)):
    y=0
    while (y<len(adjacencies[x])):
        tup=(x,int(adjacencies[x][y]))
        tuplList.append(tup)
        y+=1
    x+=1

nodeList=[]
i=0
while(i<int(lines[0])):
    nodeList.append(i)
    i+=1


theSet = set(zip(nodeList, nodeList))
cartesian = [i for i in itertools.product(nodeList, nodeList) if i not in theSet]

cartesian = [x for x in cartesian if x not in tuplList]



cartesianAdjacency={} #connected tuples (each index has those connected)
i=0
while (i<len(cartesian)): #slow, one by the rest
    j=0
    listConnections=[]
    while (j<len(cartesian)): #the rest

        # print (graph[str(cartesian[i][0])])
        if ( (str(cartesian[j][0]) in graph[str(cartesian[i][0])]) and (str(cartesian[j][1]) in graph[str(cartesian[i][1])]) ):
            if (cartesian[j]!=cartesian[i]):
                listConnections.append(cartesian[j])
                cartesianAdjacency[cartesian[i]]=cartesian[j]
        j+=1
    cartesianAdjacency[cartesian[i]]=listConnections
    i+=1






#https://stackoverflow.com/questions/8922060/how-to-trace-the-path-in-a-breadth-first-search
def bfs(start, end):
    queue = []
    queue.append([start])
    while queue:
        path = queue.pop(0)
        node = path[-1]
        if node == end:
            return path
        for adjacent in cartesianAdjacency.get(node):
            new_path = list(path)
            new_path.append(adjacent)
            queue.append(new_path)


tuple1=( (int(lines2[1]) , int(lines2[2])) )
tuple2=((int(lines2[3]),int(lines2[4])))
theBFS=(bfs(tuple1,tuple2))
lukesPath=""
lorelaisPath=""
i=0
while (i<len(theBFS)):
    lukesPath+=str(((theBFS[i][0])))+" "

    lorelaisPath+=str(((theBFS[i][1])))+" "
    i+=1


print (lukesPath)
print (lorelaisPath)