{"problem":{"name":"Mediator","description":{"content":"**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 $","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":3000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc350_g"},"statements":[{"statement_type":"Markdown","content":"**Beware the special input format and the smaller memory limit than usual.**\nThere is an undirected graph with vertices $1, 2, \\dots, N$, initially without edges.  \nYou need to process the following $Q$ queries on this graph:\n  \n\n1 $u$ $v$\n\nType $1$: Add an edge between vertices $u$ and $v$.  \nBefore adding the edge, $u$ and $v$ belong to different connected components (i.e., the graph always remains a forest).\n  \n\n2 $u$ $v$\n\nType $2$: If there is a vertex adjacent to both $u$ and $v$, report its vertex number; otherwise, report $0$.  \nGiven that the graph always remains a forest, the answer to this query is uniquely determined.\n  \n\nThe queries are given in an encrypted form.  \nThe original query is defined by three integers $A, B, C$, and the encrypted query is given as three integers $a, b, c$.  \nLet $X_k$ be the answer to the $k$\\-th type-$2$ query. Define $X_k = 0$ for $k = 0$.  \nRestore $A, B, C$ from the given $a, b, c$ as follows:\n\n*   Let $l$ be the number of type-$2$ queries given before this query (not counting the query itself). Then, use the following:\n    *   $A = 1 + (((a \\times (1+X_l)) \\mod 998244353) \\mod 2)$\n    *   $B = 1 + (((b \\times (1+X_l)) \\mod 998244353) \\mod N)$\n    *   $C = 1 + (((c \\times (1+X_l)) \\mod 998244353) \\mod N)$\n\n## Constraints\n\n*   All input values are integers.\n*   $2 \\le N \\le 10^5$\n*   $1 \\le Q \\le 10^5$\n*   $1 \\le u < v \\le N$\n*   $0 \\le a,b,c < 998244353$\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$ $Q$\n$\\rm{Query}$$_1$\n$\\rm{Query}$$_2$\n$\\vdots$\n$\\rm{Query}$$_Q$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc350_g","tags":[],"sample_group":[["6 12\n143209915 123840720 97293110\n89822758 207184717 689046893\n67757230 270920641 26993265\n952858464 221010240 871605818\n730183361 147726243 445163345\n963432357 295317852 195433903\n120904472 106195318 615645575\n817920568 27584394 770578609\n38727673 250957656 506822697\n139174867 566158852 412971999\n205467538 606353836 855642999\n159292205 319166257 51234344","0\n2\n0\n2\n6\n0\n1\n\nAfter decrypting all queries, the input is as follows:\n\n6 12\n2 1 3\n1 2 6\n1 2 4\n1 1 3\n2 4 6\n2 1 4\n1 5 6\n1 1 2\n2 1 4\n2 2 5\n2 3 4\n2 2 3\n\nThis input has a $6$\\-vertex graph and $12$ queries.\n\n*   The first query is `2 1 3`.\n    *   No vertex is adjacent to both vertex $1$ and vertex $3$, so report $0$.\n*   The second query is `1 2 6`.\n    *   Add an edge between vertices $2$ and $6$.\n*   The third query is `1 2 4`.\n    *   Add an edge between vertices $2$ and $4$.\n*   The fourth query is `1 1 3`.\n    *   Add an edge between vertices $1$ and $3$.\n*   The fifth query is `2 4 6`.\n    *   The vertex adjacent to both vertices $4$ and $6$ is vertex $2$.\n*   The sixth query is `2 1 4`.\n    *   No vertex is adjacent to both vertices $1$ and $4$, so report $0$.\n*   The seventh query is `1 5 6`.\n    *   Add an edge between vertices $5$ and $6$.\n*   The eighth query is `1 1 2`.\n    *   Add an edge between vertices $1$ and $2$.\n*   The ninth query is `2 1 4`.\n    *   The vertex adjacent to both vertices $1$ and $4$ is vertex $2$.\n*   The tenth query is `2 2 5`.\n    *   The vertex adjacent to both vertices $2$ and $5$ is vertex $6$.\n*   The eleventh query is `2 3 4`.\n    *   No vertex is adjacent to both vertices $3$ and $4$, so report $0$.\n*   The twelfth query is `2 2 3`.\n    *   The vertex adjacent to both vertices $2$ and $3$ is vertex $1$."],["2 1\n377373366 41280240 33617925","The output may be empty."]],"created_at":"2026-03-03 11:01:13"}}