#include <iostream.h>
#include <fstream.h>

const int MAX_N = 100;              // 最多的節點數目
const char* INPUT_FILE = "Graph.txt";


struct Graph {
    int NodeCount;                  // 節點的數目
    int AdjMatrix[MAX_N][MAX_N];    // 鄰接矩陣,如果圖中i,j相鄰則G[i][j]>0，否則G[i][j]=0
};

typedef int Path[MAX_N];            // 用來存儲路徑
    
typedef bool Mark[MAX_N];          // 標記訪問過的節點


void PrintPath(Path& path, int length) {        // 打印路徑
    for (int i = 0; i < length; i++) {
        cout << path[i] << " ";
    }
    cout << endl;
}

// 深度優先搜索
// G 輸入的圖，
// path用來記錄路徑
// visited 用來標記搜索過的節點，初始化全部為false
// v 當前的節點
// T 目的節點
// length 目前已經得到的路徑的長度
void SearchAllPath(const Graph& G, Path& path, Mark& visited, int v, int des, int length) {
    if (visited[v]) return;
    path[length-1] = v;
    if (v == des) {
        PrintPath(path, length);
    } else {
        visited[v] = true;
        for (int i = 0; i < G.NodeCount; i++) 
            if (G.AdjMatrix[v][i] != 0 && !visited[i]) {                
                SearchAllPath(G, path, visited, i, des, length+1);
            }
        visited[v] = false;
    }
}


void ReadData(Graph& G, int& src, int& des)  //讀入數據
{
    ifstream fin(INPUT_FILE);
    fin >> G.NodeCount >> src >> des;      // 讀入節點數目，起點終點，節點從0開始標號
    for (int i = 0; i < G.NodeCount; i++) 
        for (int j = 0; j < G.NodeCount; j++) {
            fin >> G.AdjMatrix[i][j];
        }
}

int main()
{
    
    Graph G;
    int src, des;          // 起點和終點    
    Path path;              // 存儲路徑
    Mark visited;          // 訪問標記
    ReadData(G, src, des);  //讀入數據

    for (int i = 0; i < G.NodeCount; i++) visited[i] = false;  // 初始化
    SearchAllPath(G, path, visited, src, des, 1);  
    
    return 0;
}