#/***********************************************************
#    warshall.rb -- 推移的閉包
#    使用例: ruby warshall.rb <warshall.dat
#***********************************************************/

NMAX = 100
row = []; (NMAX + 1).times { row.push(0) }
$adjacent = []; (NMAX + 1).times { $adjacent.push(row.dup) }

def readgraph                            # データ入力 
    if ((n = gets.to_i) == 0 || n > NMAX) 
        n = 0;  return
    end
    for i in 1..n
        for j in 1..n; $adjacent[i][j] = 0; end
        $adjacent[i][i] = 1
    end
    while ((s = gets) != nil && s.index(/(\d+)\s+(\d+)/) != nil)
        $adjacent[$1.to_i][$2.to_i] = 1
    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

n = readgraph()
for k in 1..n
    for i in 1..n
        if ($adjacent[i][k] == 1)
            for j in 1..n
                $adjacent[i][j] |= $adjacent[k][j]
            end
        end
    end
end
printf("推移的閉包:\n")
for i in 1..n
    for j in 1..n; printf(" %d", $adjacent[i][j]); end
    printf("\n")
end

exit 0