← 返回题目
题库练习 关系网络
← 上一题 下一题 →

A1496 | 关系网络

时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

有 $n$ 个人，每个人的编号为 $1,2,\dots,n-1,n$。

有一些人相互认识，如果现在 $x$ 想要认识 $y$，那么他可以通过他所认识的人来认识更多的人。

例: 如果 $a$ 认识 $b$、$b$ 认识 $c$，那么 $a$ 可以通过 $b$ 来认识 $c$ 。

现在需要你求出 $x$ 最少需要通过多少人才能认识 $y$。

### 数据范围

$1 \leq n \leq 100$
$0 \leq a_{i,j} \leq 1$

输入格式

第一行输入三个整数$n,x,y$。

随后输入$n$行,每行输入$n$个整数,代表存在着一个大小为$N \times N$的邻接矩阵 $a$ ，且任意两数之间带有空格。

若$a_{i,j} = 1$,则代表$i$认识$j$。

若$a_{i,j} = 0$,则代表$i$不认识$j$。

输出格式

输出一行一个数，表示 $x$ 认识 $y$ 最少需要通过的人数。

输入输出样例

输入 #1
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
输出 #1
2
C++ 编辑器
输入
输出