问题2166--六度空间

2166: 六度空间

时间限制: 1Sec 内存限制:128 MB
提交:16 解决:11
[ 状态] [ 讨论版] [ 提交] [命题人: ]
题目描述

六度空间理论是说你和任何一个陌生人之间所间隔的人不会超过六个,也就是说,最多通过五个中间人你就能够认识任何一个陌生人。现在有n个人,m条关系。求n个人中是否任意两个人都满足六度空间。

输入
第一行一个数字T (0
随后T组测试数据,对于每组测试数据第一行两个数字n,m,分别表示n个人,m条关系。随后m行,每行两个数字s,t,表示s和t认识。(2 <= n <= 9, 0 <= m <= n*n),(1 <= s,t <= n)

输出

对于每组数据,如果满足六度空间,则输出"yes",否则输出"no"。注:如果两个人不能通过中间人相识,则不满足六度空间。

样例输入 Copy
2 8 7 1 2 2 3 3 4 4 5 5 6 6 7 7 8 7 6 1 2 2 3 3 4 4 5 5 6 6 7
样例输出 Copy
no yes
来源/分类