103506: [Atcoder]ABC350 G - Mediator

Problem Statement

Beware the special input format and the smaller memory limit than usual.

There is an undirected graph with vertices $1, 2, \dots, N$, initially without edges.
You need to process the following $Q$ queries on this graph:

1 $u$ $v$

Type $1$: Add an edge between vertices $u$ and $v$.
Before adding the edge, $u$ and $v$ belong to different connected components (i.e., the graph always remains a forest).

2 $u$ $v$

Type $2$: If there is a vertex adjacent to both $u$ and $v$, report its vertex number; otherwise, report $0$.
Given that the graph always remains a forest, the answer to this query is uniquely determined.

The queries are given in an encrypted form.
The original query is defined by three integers $A, B, C$, and the encrypted query is given as three integers $a, b, c$.
Let $X_k$ be the answer to the $k$-th type-$2$ query. Define $X_k = 0$ for $k = 0$.
Restore $A, B, C$ from the given $a, b, c$ as follows:

• Let $l$ be the number of type-$2$ queries given before this query (not counting the query itself). Then, use the following:
  • $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)$

Constraints

• All input values are integers.
• $2 \le N \le 10^5$
• $1 \le Q \le 10^5$
• $1 \le u < v \le N$
• $0 \le a,b,c < 998244353$

Input

The input is given from Standard Input in the following format:

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

Output

Let $k$ be the number of type-$2$ queries. Print $k$ lines.
The $i$-th line should contain the answer to the $i$-th type-$2$ query.

Sample Input 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

Sample Output 1

0
2
0
2
6
0
1

After decrypting all queries, the input is as follows:

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

This input has a $6$-vertex graph and $12$ queries.

• The first query is 2 1 3.
  • No vertex is adjacent to both vertex $1$ and vertex $3$, so report $0$.
• The second query is 1 2 6.
  • Add an edge between vertices $2$ and $6$.
• The third query is 1 2 4.
  • Add an edge between vertices $2$ and $4$.
• The fourth query is 1 1 3.
  • Add an edge between vertices $1$ and $3$.
• The fifth query is 2 4 6.
  • The vertex adjacent to both vertices $4$ and $6$ is vertex $2$.
• The sixth query is 2 1 4.
  • No vertex is adjacent to both vertices $1$ and $4$, so report $0$.
• The seventh query is 1 5 6.
  • Add an edge between vertices $5$ and $6$.
• The eighth query is 1 1 2.
  • Add an edge between vertices $1$ and $2$.
• The ninth query is 2 1 4.
  • The vertex adjacent to both vertices $1$ and $4$ is vertex $2$.
• The tenth query is 2 2 5.
  • The vertex adjacent to both vertices $2$ and $5$ is vertex $6$.
• The eleventh query is 2 3 4.
  • No vertex is adjacent to both vertices $3$ and $4$, so report $0$.
• The twelfth query is 2 2 3.
  • The vertex adjacent to both vertices $2$ and $3$ is vertex $1$.

Sample Input 2

2 1
377373366 41280240 33617925

Sample Output 2

The output may be empty.

问题描述

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

有一个无向图，包含顶点$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$行，其中$k$是类型$2$查询的数量。
第$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

输出可能是空的。