#6611. Trisolaris:ゼロから始める OI 生活 联动题

内存限制:256 MiB 时间限制:1250 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Snakes

题目描述

谨以此题,纪念 Trisolaris。

Snakes 听说过三体,也听说过 Trisolaris 这个词。Trisolaris 应是从代表「三」的词根前缀 tri- 和代表「太阳」的 solaris 结合而成的词。

Snakes 开始发挥他的想象:既然是三体问题,那么不如研究天体间的联系。

Snakes 认为,依据性质的变化,两个天体间的关联程度会发生变化,导致天体之间的关联关系动态变化。抽象地,我们可以将天体看作点,将关联的两个天体之间连边,那么我们可以得到一个无向图。

Snakes 定义一个无向图是一个合法的 Trisolaris 图,当且仅当无向图无重边与自环,且无向图的每个联通块均为下列之一:

  • 树(特别地,我们认为一个独立的点也是树)
  • 三元环(三个点的联通块,两两之间有且仅有一条边)

现在,Snakes 在观测一个有 n 个天体的星座,天体编号为 1 n 。这也意味着无向图的结点数为 n 。初始时,天体之间无任何关联关系。

观测时 Snakes 会随时给出下列两种操作:

  • 1 u v 表示编号为 u v 的天体间产生关联关系,无向图中新增一条边连接编号 u v 的结点。

  • 2 u v 表示编号为 u v 的天体间关联关系消失,无向图中删去一条连接编号 u v 结点的边。

操作总计 m 个。

你需要帮助 Snakes 动态维护这个无向图,并且每次操作后回答当前图是否为合法的 Trisolaris 图,若是,请输出一行 Yes,否则请输出一行 No

由于某些需要,Snakes 可能会强制在线,具体请阅读【输入格式】部分。

输入格式

从标准输入中读取数据。

第一行,两个整数 n,m,x ,表示无向图点数,边数,是否强制在线参数。

接下来 m 行,每行一个操作 o,u,v ,表示操作类型,与边两端结点的编号,具体请阅读【题目描述】部分。

x=1 ,则结点编号需要异或此前所有操作结束后合法图的个数,也即输出的 Yes 的个数。

否则不需要对输入数据作任何处理。

输出格式

输出数据到标准输出中。

输出 m 行,每行包含 YesNo,表示当前操作后当前无向图是否为合法的 Trisolaris 图。

样例

样例 1 输入

5 20 0
1 1 2
1 2 3
1 1 3
1 4 5
1 3 4
2 1 3
2 2 3
1 3 5
1 2 4
2 2 4
2 1 2
2 3 4
2 3 5
2 4 5
1 1 5
1 5 4
1 1 2
1 2 3
1 3 4
2 3 4

样例 1 输出

Yes
Yes
Yes
Yes
No
Yes
Yes
Yes
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes

样例 1 解释

第 5 个操作后,无向图为 (1,2,3) 形成三元环,(3,4),(4,5) 间有连边。

第 9 个操作后,无向图为 (3,4,5) 形成三元环,(1,2),(2,4) 间有连边。

第 19 个操作后,无向图为 (1,2),(2,3),(3,4),(4,5),(1,5) 间有连边。

样例 2

见附加文件中 trisolar2.intrisolar2.out。此样例满足子任务 1 的限制。

样例 3

见附加文件中 trisolar3.intrisolar3.out。此样例满足子任务 2 的限制。

样例 4

见附加文件中 trisolar4.intrisolar4.out。此样例满足子任务 3 的限制。

样例 5

见附加文件中 trisolar5.intrisolar5.out。此样例满足子任务 4 的限制。

样例 6

见附加文件中 trisolar6.intrisolar6.out。此样例满足子任务 5 的限制。

数据范围与提示

子任务 1( 10\% ): 1\leq n,m\leq 10 ,不强制在线,保证给定任一操作结束后无向图均无重边与自环。

子任务 2( 20\% ): 1\leq n\leq 1000 1\leq m\leq 5000 ,不强制在线,保证给定任一操作结束后无向图均无重边与自环。

子任务 3( 30\% ): 1\leq n\leq 2\times 10^5 1\leq m\leq 5\times 10^5 ,不强制在线,保证给定任一操作结束后无向图均无重边与自环。

子任务 4( 30\% ): 1\leq n\leq 2\times 10^5 1\leq m\leq 5\times 10^5 ,强制在线,保证给定任一操作结束后无向图均无重边与自环。

子任务 5( 10\% ): 1\leq n\leq 2\times 10^5 1\leq m\leq 5\times 10^5 ,强制在线,不保证无向图无重边与自环。

对于全部数据, 1\leq u,v\leq n\leq 2\times 10^5 1\leq m\leq 5\times 10^5 0\leq x\leq 1 1\leq o\leq 2 ,不保证无向图无重边与自环。