#/***********************************************************
#    toposort.rb -- トポロジカル・ソーティング
#    使用例: ruby toposort.rb <toposort.dat
#***********************************************************/

NMAX = 100
$adjacent = (0..NMAX).collect {Array.new(NMAX + 1)}  # 隣接行列 
$visited = []                                        # 訪れたか 



def readgraph                            # データ入力 
    n = gets.to_i
    if (n == 0 || n > NMAX) 
        n = 0;  return
    end
    for i in 1..n
        for j in 1..n; $adjacent[i][j] = 0; end
    end
    while (line = gets)
        i, j = line.scan(/\d+/); i = i.to_i; j = j.to_i 
        if (i > 0 && j > 0)
            $adjacent[i][j] = 1
        end
    end
    printf("隣接行列:\n")
    for i in 1..n
        for j in 1..n; printf(" %d", $adjacent[i][j]); end
        printf("\n")
    end
    return n
end

NEVER = 1; JUST = 2; ONCE = 3

def visit(i, n)
    $visited[i] = JUST
    for j in 1..n
        if ($adjacent[j][i] != 1); next; end
        if ($visited[j] == NEVER)
            visit(j, n)
        elsif
            $visited[j] == JUST 
            printf("\nサイクルあり!n");  exit 1
        end
    end
    $visited[i] = ONCE;  printf(" %d", i)
end

n = readgraph()  # データ \tt nend, \tt adjacent[1..n][1..n]end を読む 
for i in 1..n; $visited[i] = NEVER; end
printf("トポロジカル・ソーティングの結果:\n")
for i in 1..n
    if ($visited[i] == NEVER); visit(i, n); end
end
printf("\n")

exit 0