#P1288. 是不是亲戚
是不是亲戚
Description
若某个家族人员过于庞大,要判断两个是否是亲戚,确实还很不容易,现在给出某个亲戚关系图,求任意给出的两个人是否具有亲戚关系。
规定:x 和 y 是亲戚,y 和 z 是亲戚,那么 x 和 z 也是亲戚。如果 x,y 是亲戚,那么 x 的亲戚都是 y 的亲戚,y 的亲戚也都是 x 的亲戚。
Input Format
输入由两部分组成。
第一部分以N,M开始。N为问题涉及的人的个数(1<=N<=20000)。这些人的编号为1,2,3,…, N。下面有M行(1<= M <= 1 000 000),每行有两个数ai, bi,表示已知ai和bi是亲戚。
第二部分以Q开始。以下Q行有Q个询问(1<=Q<=1 000 000),每行为ci, di,表示询问ci和di是否为亲戚。
<math xm<math xm<math xm<math xm
Output Format
P行,每行一个Yes
或 No
。表示第 <math xmlns="http://www.w3.org/1998/Math/MathML">i 个询问的答案为“具有”或“不具有”亲戚关系。
6 5
1 2
1 5
3 4
5 2
1 3
3
1 4
2 3
5 6
Yes
Yes
No