2543: 关系网络

内存限制:256 MB 时间限制:1.000 S
评测方式:文本比较 命题人:
提交:139 解决:63

题目描述

n个人,他们的编号为1~n,其中有一些人相互认识,现在j想要认识k,可以通过他所认识的人来认识更多的人(如果a认识bb认识c,那么a可以通过b来认识c),求出x最少需要通过多少人才能认识y

 

输入

第一行三个整数nxy,接下来一个n×n的邻接矩阵,a[i,j]=1表示i认识j0表示不认识。保证i=j,a[i,j]=0,并且a[i,j]=a[j,i]

 

输出

x认识y最少需要通过的人数。

 

样例输入 复制

5 1 5
0 1 0 0 0
1 0 1 1 0
0 1 0 1 0
0 1 1 0 1
0 0 0 1 0

样例输出 复制

2

提示

n<=1001<=x,y<=n,x<>y