题目描述

给定一张点数为n的有向图的邻接矩阵，图中不包含自环，求该有向图的传递闭包。

一张图的邻接矩阵定义为一个n×n的矩阵A=(aij)n×n，见下图：

一张图的传递闭包定义为一个n×n的矩阵B=(bij)n×n，见下图：

输入格式

输入数据共n+1行。

第一行一个正整数n(1≤n≤20)；

第2到n+1行每行n个整数，第i+1行第j列的整数为aij。

输出格式

输出数据共n行。

第1到n行每行n个整数，第i行第j列的整数为bij。

输入/输出样例

4
0 0 0 1
1 0 0 0
0 0 0 1
0 1 0 0

1 1 0 1
1 1 0 1
1 1 0 1
1 1 0 1

说明/提示

时间1000ms，内存256MiB