#P3082. Graph2

    ID: 2220 传统题 1000ms 512MiB 尝试: 54 已通过: 13 难度: 6 上传者: 标签>CF2100提高+/省选-线段树分治活跃时间区间挂树可撤销并查集按大小合并

Graph2

题目描述

一个无向图,nn 个点,编号从 1∼n1\sim n,mm 条边,编号从 1∼m1\sim m。接下来 qq 个操作:

  • 插入一条边,编号为原有编号数 +1+1;
  • 删除一条边,编号数不变;
  • 询问两个点是否能够互达。

输入格式

第一行两个整数 n,mn,m。

接下来 mm 行,每行两个整数,表示该条边所连接的两个点。

接下来一行一个整数 qq。

接下来 qq 行,是以下三种之一:

  • D x,表示删除编号为 xx 的边(一条边被删除多次等价于删除一次);
  • I x y,表示在点 xx 和点 yy 之间插入一条边;
  • Q x y,表示询问点 xx 和点 yy 是否能互达;

保证点和边的编号合法。

输出格式

对于每个询问输出一行,Yes 表示能达到,No 表示不能。

2 1
1 2
5
Q 1 2
D 1
Q 1 2
I 1 2
Q 1 2
Yes
No
Yes

数据规模与约定

对于 100%100\% 的数据,1≤n≤5×1041\le n\le 5\times 10^4,1≤m,q≤1051\le m,q\le 10^5。