#Breadth first search
class queue():
    def __init__(self):
        self.array = []
    def push(self, data):
        self.array.append(data)
    def pop(self):
        if not self.array:
            return
        del self.array[0]
    def top(self):
        return self.array[0]
    def isEmpty(self):
        if not self.array:
            return True
        return False

def bfs(m, q, result, visited):
    #If q is not empty
    if not q.isEmpty():
        #Pop the top element
        t = q.top()
        q.pop()
        #Add it to result
        result.append(t)
        #Add all its adjacent unvisited elements to the q
        for adjacentElement in range(9):
            if(m[t][adjacentElement] == 1 and visited[adjacentElement] == 0):
                #Mark it visited
                visited[adjacentElement] = 1
                #Add it to the q
                q.push(adjacentElement)
        bfs(m, q, result, visited)
    return result

def foo(matrix):
    q = queue()
    q.push(0)
    v = [0 for col in range(9)]
    v[0] = 1
    r = bfs(matrix, q, [], v)
    print r

#Main Program
matrix = [[0 for col in range(9)] for row in range(9)]
matrix[0][1] = 1
matrix[0][8] = 1
matrix[1][0] = 1
matrix[8][0] = 1
matrix[8][2] = 1
matrix[8][6] = 1
matrix[2][3] = 1
matrix[2][4] = 1
matrix[2][5] = 1
matrix[2][8] = 1
matrix[3][2] = 1
matrix[4][2] = 1
matrix[4][7] = 1
matrix[5][2] = 1
matrix[5][6] = 1
matrix[6][8] = 1
matrix[6][5] = 1
matrix[7][4] = 1
matrix[7][6] = 1
foo(matrix)