← 返回题目列表

AtCoder · abc350_g

G. 调解员

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

请注意特殊的输入格式和比平常更小的内存限制。

有一个带顶点的无向图 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 查询。定义 X_k = 0 为 k = 0.
恢复 A, B, C 从给定的 a, b, c 如下:

  • 让 l 是类型的数量-2 在此查询之前给出的查询(不包括查询本身)。然后,使用以下命令:
    • 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)

约束

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

输入

输入由标准输入按以下格式给出:

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

输出

让 k 是类型的数量-2 查询。打印 k 行。
的 i- 第行应包含以下问题的答案 i-第类型-2 查询。


示例输入 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

解密所有查询后,输入如下:

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 查询。

  • 第一个查询是 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.

示例输入 2

2 1
377373366 41280240 33617925

示例输出 2


输出可能为空。