#P16941. [SGU336]Elections

[SGU336]Elections

题目描述

Berland 即将举行议会选举。最初有 NN 个政党。若存在有向关系 a→ba\to b,表示政党 aa 掌握关于政党 bb 的不利信息。

若若干政党或已有选举联盟合并成一个新的联盟,则:

  • 新联盟掌握原来各成员掌握的全部信息;
  • 原来任何关于这些成员的不利信息,都改为关于新联盟的信息;
  • 一个政党或联盟可能掌握关于自己的信息。

初始政党编号为 1∼N1\sim N。每次合并会产生一个新的联盟,依次编号为 N+1,N+2,…N+1,N+2,\ldots。

你需要依次处理两类操作:

  • 1 a b:询问当前实体 aa 是否掌握关于当前实体 bb 的不利信息;
  • 2 a b:将当前实体 a,ba,b 合并为一个新联盟。

输入格式

第一行两个整数 N,MN,M,满足 1≤N≤1051\le N\le10^5,1≤M≤2⋅1051\le M\le2\cdot10^5。

接下来 MM 行,每行两个整数 a,ba,b,表示初始关系 a→ba\to b。

下一行一个整数 QQ,1≤Q≤2⋅1051\le Q\le2\cdot10^5。

接下来 QQ 行,每行一个操作。所有操作中的编号都引用当前存在的政党或联盟;对于 2 a b 保证 a≠ba\ne b。

输出格式

对每个第一类询问输出一行 YES 或 NO。

样例

4 6
1 2
1 3
3 2
4 4
2 4
1 2
4
1 3 4
2 2 3
1 5 4
1 4 5
NO
YES
NO