Problem1094--「一本通 3.5 练习 2」消息的传递

1094: 「一本通 3.5 练习 2」消息的传递

Time Limit: 1 Sec  Memory Limit: 512 MB
Submit: 0  Solved: 0
Submit Status Web Board

Creator:

Description

我们的郭嘉大大在曹操这过得逍遥自在,但是有一天曹操给了他一个任务,在建邺城内有 NNN 个袁绍的奸细,将他们从 111NNN 进行编号,同时他们之间存在一种传递关系,即若Ci,j=1C_{i,j}=1Ci,j=1,则奸细 iii 能将消息直接传递给奸细 jjj

现在曹操要发布一个假消息,需要传达给所有奸细,而我们的郭嘉大大则需要传递给尽量少的奸细使所有的奸细都知道这一个消息,问我们至少要传给几个奸细?


Input

文件的第一行为 NNN,第二行至第 N+1N+1N+1 行为 N×NN \times NN×N 的矩阵(若第 III 行第 JJJ 列为 111,则奸细 III 能将消息直接传递给奸细 JJJ,若第 III 行第 JJJ 列为 000,则奸细 III 不能将消息直接传递给奸细 JJJ)。


Output

输出文件只有一行:即我们的郭嘉大大首先至少要传递的奸细个数。


Sample Input

8
0 0 1 0 0 0 0 0
1 0 0 1 0 0 0 0
0 1 0 1 1 0 0 0
0 0 0 0 0 1 0 0
0 0 0 1 0 0 0 0
0 0 0 1 0 0 0 0
0 0 0 1 0 0 0 1
0 0 0 0 0 0 1 0

Sample Output

2

HINT

N≤1000N \le 1000N1000


Source/Category


Submit Status