← 返回题目列表

AtCoder · tessoku_book_em

B66. 台风

中文机器翻译题面 查看原题

配点: 1000 点

問題文

在 ALGO 国家 N 站和 M 有几条铁路线。 在车站 它们的编号最大为 1 减去 N 。i 主线是站 A_i 和车站 B_i 双向连接。 另外,今天台风将登陆ALGO国家,部分航线可能会暂停。 关于这一点,下面 处理类型为 2 的查询。

  • 查询1:x 主要路线将暂停。
  • 查询2:此刻站 s 从车站 t 。

给出的查询数 Q ,计算量为 优选 O((N+M+Q)\log N) 。

制約

  • 2 \leq N \leq 100000
  • 1 \leq M \leq 100000
  • 1 \leq Q \leq 100000
  • 1 \leq A_i \lt B_i \leq N\ (1\leq i\leq M)
  • i \neq j \implies (A_i,B_i) \neq (A_j,B_j)
  • \operatorname{Query}_i\ (1\leq i\leq Q) 均采用以下格式之一:
    • 1 x (1\leq x\leq M) 但是,在给出此查询之前 x 主线从未暂停过。
    • 2 u v (1\leq u\lt v\leq N)
  • 所有输入均为整数

入力

输入是按以下格式从标准输入给出的。

N M
A_1 B_1
A_2 B_2
\vdots
A_M B_M
Q
\operatorname{Query}_1
\operatorname{Query}_2
\vdots
\operatorname{Query}_Q

出力

查询 2 的答案。


入力例 1

3 2
1 2
2 3
4
2 2 3
1 2
2 1 3
1 1

出力例 1

Yes
No

查询 1 ,图表发生如下变化:


入力例 2

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

出力例 2

No
Yes
Yes
No
No

入力例 3

4 3
1 2
2 3
3 4
7
2 1 2
2 1 3
2 1 4
1 2
2 1 2
2 1 3
2 1 4

出力例 3

Yes
Yes
Yes
Yes
No
No