Responsive image

问题 E: 朋友

问题 E: 朋友

时间限制: 1 Sec  内存限制: 128 MB
提交: 0  解决: 36
[提交][状态][讨论版][命题人:]

题目描述

据说世界上所有的人通过六个朋友关系，能够认识世界上的所有人，即你想认识一个陌生人，你会先去询问你的朋友，若你的朋友认识他，则你也就认识他了，若你的朋友不认识他，则他会去询问他的朋友，若他的朋友认识，则你也就认识了，若不认识他会去询问他朋友的朋友，以此类推通过六个朋友关系，就能够认识世界上的所有人了。现在我们假设它是真的，规定：a和b是朋友，b和c是朋友，那么a和c也是朋友。如果a，b是朋友，那么a的朋友都是b的朋友，b的朋友也都是a的朋友。给你n对关系，小劉有x次询问，现在小劉想知道他询问的人是否跟他有朋友关系（小劉用1表示）。

输入描述

第一行给出三个整数n，x，m。n表示给你n对关系，x表示给你x次询问，m表示一共有m个人，（1<=n,x<=5000,1<=m<=100）
接下来n行，每行两个整数a，b，表示a和b有朋友关系（1<=a,b<=m）
然后x行，每行一个整数p，表示询问p和小劉是否具有朋友关系

输出描述

输出x行，每行判断p和小劉是否具有朋友关系，如果有朋友关系则输出Yes，否则输出No

样例输入

6 3 8
1 2
2 3
3 4
4 5
5 6
6 7
2
5
8

样例输出

Yes
Yes
No

提示

给出六组关系，第一组表示1和2有朋友关系，第一组表示2和3有关系，第一组表示3和4有关系，第一组表示4和5有关系，第一组表示5和6有关系，第一组表示6和7有关系，根据规定，1，2，3，4，5，6，7都具有朋友关系

给出了x次询问

1和2具有朋友关系，输出Yes

1和5具有朋友关系，输出Yes

1和8没有具有朋友关系，输出No

[提交][状态]
ACM算法攻关部