6594 - 消息的传递

我们的郭嘉大大在曹操这里过得逍遥自在,但是有一天曹操给了他一个任务,在建邺城内有N(N≤1000)个袁绍的侦探,将他们从1到N行进行编号,同时他们之间存在一种传递关系,即若C[i,j]=1,则侦探i能将消息直接传递给侦探j。

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

输入

第一行为N,第二行至第N+1行为N*N的矩阵(若第i行第j列为1,则侦探i能将消息直接传递给侦探j,若第i行第j列为0,则侦探i不能将消息直接传递给侦探j)。

输出

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

样例

输入

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

输出

2

来源

一本通提高

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题