/ 
Time Limit: 3 sec / Memory Limit: 256 MB
配点 : 600 点
問題文
特殊な入力形式に注意してください。 また、メモリ制限が通常より小さいことに注意してください。
頂点 1,2,\dots,N の N 頂点からなる無向グラフがあり、最初辺はありません。
このグラフに対して、以下の Q 個のクエリを処理してください。
1 u v
タイプ 1 : 頂点 u と頂点 v との間に辺を追加する。
辺を追加する前の時点で、 u と v は異なる連結成分に属する。(すなわち、グラフは常に森である。)
2 u v
タイプ 2 : 頂点 u と頂点 v の双方に隣接する頂点があるならその番号を答え、無ければ 0 と答える。
グラフが常に森であることから、このクエリに対する解答は一意に定まることが示せる。
但し、上記のクエリは暗号化して与えられます。
本来のクエリは 3 つの整数 A,B,C として定義され、これをもとに暗号化されたクエリが 3 つの整数 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)) \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
入力
入力は以下の形式で標準入力から与えられる。
但し、 \rm{Query}_i は i 個目のクエリを表す。
N Q
\rm{Query}_1
\rm{Query}_2
\vdots
\rm{Query}_Q
出力
タイプ 2 のクエリの個数を k としたとき、全体で k 行出力せよ。
そのうち i 行目には、タイプ 2 のクエリのうち、先頭から i 個目のものに対する解答を出力せよ。
入力例 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 個のクエリが含まれます。
- 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
2 1 377373366 41280240 33617925
出力例 2
出力が空である場合もあります。
Score: 600 points
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.