TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P1205
  • 题目
  • P1205亲戚
    限制 : 时间限制 : 20000 MS   空间限制 : 65536 KB
    问题描述

    或许你并不知道,你的某个朋友是你的亲戚。他可能是你的曾祖父的外公的女
    婿的外甥女的表姐的孙子。如果能得到完整的家谱,判断两个人是否亲戚应该是可
    行的,但如果两个人的最近公共祖先与他们相隔好几代,使得家谱十分庞大,那么
    检验亲戚关系实非人力所能及。在这种情况下,最好的帮手就是计算机。

      为了将问题简化,你将得到一些亲戚关系的信息,如同Marry和Tom是亲戚,
    Tom和Ben是亲戚,等等。从这些信息中,你可以推出Marry和Ben 是亲戚。请写一个
    程序,对于我们的关于亲戚关系的提问,以最快的速度给出答案。

    输入格式

    输入由两部分组成。

      第一部分以N,M开始。N为问题涉及的人的个数(1 ≤ N ≤ 20000)。这些人的
    编号为1,2,3,…,N。下面有M行(1 ≤ M ≤ 100000),每行有两个数ai, bi,表示
    已知ai和bi是亲戚。

      第二部分以Q开始。以下Q行有Q个询问(1 ≤ Q ≤ 1 000 000),每行为ci,
    di,表示询问ci和di是否为亲戚。

    输出格式

    对于每个询问ci, di,若ci和di为亲戚,则输出yes,否则输出no。

    样例输入

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

    样例输出

    yes
    no
    yes