AT_abc350_g [ABC350G] Mediator

题目描述

请注意特殊的输入格式。同时，请注意内存限制比通常更小。

有一个包含 $N$ 个顶点 $1,2,\dots,N$ 的无向图，初始时没有任何边。
请对该图处理以下 $Q$ 个查询。

1 $u$ $v$

类型 $1$：在顶点 $u$ 和顶点 $v$ 之间添加一条边。
在添加边之前，$u$ 和 $v$ 属于不同的连通分量（也就是说，图始终是一片森林）。

2 $u$ $v$

类型 $2$：如果存在同时与顶点 $u$ 和顶点 $v$ 相邻的顶点，则输出其编号，否则输出 $0$。
由于图始终是一片森林，可以证明对于该查询的答案是唯一的。

但是，上述查询是经过加密后给出的。
原始查询由 $3$ 个整数 $A,B,C$ 定义，基于此给出加密后的查询 $a,b,c$。
对于类型 $2$ 的查询，第 $k$ 个（从前往后数）查询的答案记为 $X_k$。此外，定义 $k=0$ 时 $X_k=0$。
请根据给定的 $a,b,c$ 按如下方式解密得到 $A,B,C$：

• 设在该查询之前已经给出的类型 $2$ 查询的个数为 $l$（不包括当前查询）。此时，按如下方式解密：
  • $A = 1 + (((a \times (1+X_l)) \bmod 998244353) \bmod 2)$
  • $B = 1 + (((b \times (1+X_l)) \bmod 998244353) \bmod N)$
  • $C = 1 + (((c \times (1+X_l)) \bmod 998244353) \bmod N)$

输入格式

输入以如下格式从标准输入给出。
其中，$\rm{Query}_i$ 表示第 $i$ 个查询。

$N$ $Q$
$\rm{Query}_1$
$\rm{Query}_2$
$\vdots$
$\rm{Query}_Q$

输出格式

设类型 $2$ 的查询总共有 $k$ 个，请输出 $k$ 行。
其中第 $i$ 行输出第 $i$ 个类型 $2$ 查询的答案。

输入输出样例 #1

输入 #1

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

输出 #1

0
2
0
2
6
0
1

输入输出样例 #2

输入 #2

2 1
377373366 41280240 33617925

输出 #2

说明/提示

限制

• 所有输入均为整数。
• $2 \leq N \leq 10^5$
• $1 \leq Q \leq 10^5$
• $1 \leq u < v \leq N$
• $0 \leq a,b,c < 998244353$

样例解释 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

对于该输入，图有 $6$ 个顶点，包含 $12$ 个查询。

• 第 $1$ 个查询为 2 1 3。
  顶点 $1$ 和顶点 $3$ 没有共同相邻的顶点，输出 $0$。
• 第 $2$ 个查询为 1 2 6。
  在顶点 $2$ 和顶点 $6$ 之间添加一条边。
• 第 $3$ 个查询为 1 2 4。
  在顶点 $2$ 和顶点 $4$ 之间添加一条边。
• 第 $4$ 个查询为 1 1 3。
  在顶点 $1$ 和顶点 $3$ 之间添加一条边。
• 第 $5$ 个查询为 2 4 6。
  顶点 $4$ 和顶点 $6$ 的共同相邻顶点为顶点 $2$。
• 第 $6$ 个查询为 2 1 4。
  顶点 $1$ 和顶点 $4$ 没有共同相邻顶点，输出 $0$。
• 第 $7$ 个查询为 1 5 6。
  在顶点 $5$ 和顶点 $6$ 之间添加一条边。
• 第 $8$ 个查询为 1 1 2。
  在顶点 $1$ 和顶点 $2$ 之间添加一条边。
• 第 $9$ 个查询为 2 1 4。
  顶点 $1$ 和顶点 $4$ 的共同相邻顶点为顶点 $2$。
• 第 $10$ 个查询为 2 2 5。
  顶点 $2$ 和顶点 $5$ 的共同相邻顶点为顶点 $6$。
• 第 $11$ 个查询为 2 3 4。
  顶点 $3$ 和顶点 $4$ 没有共同相邻顶点，输出 $0$。
• 第 $12$ 个查询为 2 2 3。
  顶点 $2$ 和顶点 $3$ 的共同相邻顶点为顶点 $1$。

样例解释 2

也可能出现输出为空的情况。

由 ChatGPT 4.1 翻译