← 返回比赛
已结束 GESP巅峰赛#27
← 上一题 下一题 →

A5733 | Alice 的奇妙通信

时间限制1s
内存限制1024MB
通过 / 提交0/0

题目描述

在一片星际战场上有 $n$ 个阵地（编号 $1\sim n$）。初始时任意两阵地之间都没有通信通道。接下来按时间顺序发生 $q$ 次事件（时间从 $1$ 到 $q$ 记为第 $t$ 个时刻），每次事件为以下三类之一：

1. 1 x y —— 在阵地 $x$ 与 $y$ 之间新建一条无向通信通道。
> 允许同一对阵地之间存在多条通道；本操作会使该对阵地间的通道条数加一。
2. 2 x y —— 摧毁一条连接阵地 $x$ 与 $y$ 的通信通道。
输入保证在执行时，$x$ 与 $y$ 之间至少存在一条通道；本操作会使其通道条数减一。

3. 3 x y —— 询问此刻能否通过现有通道从阵地 $x$ 到达阵地 $y$。

与常规输出不同：将所有回答为“连通”的询问，其发生时间分别记为 $t_1,t_2,\dots$（即它们在输入中的行号/时刻）。将这些成功询问的时间做按位异或，记为
$$ X = t_1 \oplus t_2 \oplus \cdots . $$
最终只输出整数 $X$。若没有任何一次询问连通，则输出 $0$。

输入格式

* 第一行包含两个整数 $n,q$ —— 阵地数与事件数。
* 接下来 $q$ 行，每行一个事件，格式如下之一：

* 1 x y
* 2 x y
* 3 x y
其中 $1\le x,y\le n$。

输出格式

* 输出一个整数：所有连通询问时间的按位异或值；若无连通询问则输出 $0$。

输入输出样例

输入 #1
5 6
1 1 2
1 2 3
3 1 3
2 2 3
3 1 3
3 4 5
输出 #1
3
输入 #2
4 7
1 1 2
1 2 3
3 1 3
1 3 4
3 1 4
2 2 3
3 1 4
输出 #2
6
C++ 编辑器
输入
输出