Mediator

题目描述

注意特殊的输入格式以及比平时更小的内存限制。 有一个无向图，顶点为 $1, 2, \dots, N$，起初没有边。
你需要对该图处理以下 $Q$ 个查询：
1 $u$ $v$

类型 $1$：在顶点 $u$ 和 $v$ 之间添加一条边。
在添加该边之前，$u$ 和 $v$ 属于不同的连通分量（即图始终保持为一棵森林）。

2 $u$ $v$

类型 $2$：如果存在一个顶点与 $u$ 和 $v$ 都相邻，就报告其顶点编号；否则报告 $0$。
因为图始终保持为一棵森林，该查询的答案是唯一确定的。

查询以加密的形式给出。
原始查询由三个整数 $A, B, C$ 定义，而加密查询给出三个整数 $a, b, c$。
令 $X_k$ 为第 $k$ 个类型-2 查询的答案。定义对 $k = 0$ 时 $X_k = 0$。
按如下方式从给定的 $a, b, c$ 恢复 $A, B, C$：

令 $l$ 为在该查询之前给出的类型-2 查询的个数（不包括该查询本身）。 then, 使用如下公式： $A = 1 + (((a \times (1+X_l)) \mod 998244353) \mod 2)$ $B = 1 + (((b \times (1+X_l)) \mod 998244353) \mod N)$ $C = 1 + (((c \times (1+X_l)) \mod 998244353) \mod N)$

输入格式

输入以标准输入按如下格式给出： $N$ $Q$ $\rm{Query}$$_1$ $\rm{Query}$$_2$ $\vdots$ $\rm{Query}$$_Q$

输出格式

令 $k$ 为类型-2 查询的个数。输出 $k$ 行。
第 $i$ 行应包含第 $i$ 个类型-2 查询的答案。

6 12
143209915 123840720 97293110
89822758 207184717 689046893
67757230 270920641 26993265
952858464 221010240 871605818
730183361 147726243 445163345
963432357 295317852 195433903
120904472 106195318 615645575
817920568 27584394 770578609
38727673 250957656 506822697
139174867 566158852 412971999
205467538 606353836 855642999
159292205 319166257 51234344

0
2
0
2
6
0
1

6 12
2 1 3
1 2 6
1 2 4
1 1 3
2 4 6
2 1 4
1 5 6
1 1 2
2 1 4
2 2 5
2 3 4
2 2 3

提示

所有输入值均为整数。 $2 \le N \le 10^5$ $1 \le Q \le 10^5$ 1 \le u < v \le N 0 \le a,b,c < 998244353将所有查询解密后，输入如下：

该输入有一个 6 个顶点的图和 12 个查询。

第一个查询是 $2 1 3$。 没有顶点同时与顶点 $1$ 和顶点 $3$ 相邻，所以报告 $0$。

第二个查询是 $1 2 6$。 在顶点 $2$ 和 $6$ 之间添加一条边。

第三个查询是 $1 2 4$。 在顶点 $2$ 和 $4$ 之间添加一条边。

第四个查询是 $1 1 3$。 在顶点 $1$ 和 $3$ 之间添加一条边。

第五个查询是 $2 4 6$。 同时与顶点 $4$ 和 $6$ 相邻的顶点是顶点 $2$。

第六个查询是 $2 1 4$。 没有顶点同时与顶点 $1$ 和顶点 $4$ 相邻，所以报告 $0$。

第七个查询是 $1 5 6$。 在顶点 $5$ 和 $6$ 之间添加一条边。

第八个查询是 $1 1 2$。 在顶点 $1$ 和 $2$ 之间添加一条边。

第九个查询是 $2 1 4$。 同时与顶点 $1$ 和 $4$ 相邻的顶点是顶点 $2$。

第十个查询是 $2 2 5$。 同时与顶点 $2$ 和 $5$ 相邻的顶点是顶点 $6$。

第十一个查询是 $2 3 4$。 没有顶点同时与顶点 $3$ 和顶点 $4$ 相邻，所以报告 $0$。

第十二个查询是 $2 2 3$。 同时与顶点 $2$ 和顶点 $3$ 相邻的顶点是顶点 $1$。
输出可能为空。

标签: AtCoder|abc350G

来源

AtCoder|abc350G