TouchStone
  Please Login
ログイン 登録
距离明年CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • 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