题目描述

《传递闭包》

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

输入格式

输入数据共 n+1 行。 第一行一个正整数 n。 第 2 到 n+1 行每行 n 个整数，第 i+1 行第 j 列的整数为 a_ij。

输出格式

输出数据共 n 行。 第 1 到 n 行每行 n 个整数，第 i 行第 j 列的整数为 b_ij。

样例

输入样例 1

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

输出样例 1

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

输入样例 2

3
0 1 0
0 0 1
0 0 0

输出样例 2

0 1 1
0 0 1
0 0 0

输入样例 3

3
0 1 0
0 0 1
1 0 0

输出样例 3

1 1 1
1 1 1
1 1 1

输入样例 4

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

输出样例 4

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

输入样例 5

2
0 0
0 0

输出样例 5

0 0
0 0