图
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

有一个无向图，其顶点为 1,2\cdots,n，最初没有边。
您需要在这个图上进行以下两种操作：

操作 1 ：给定 u,v，将 节点 u 和节点 v 连一条长度为 1 的边。（保证在添加边之前，不存在 u 到达 v 的路径。）

操作 2 ：给定 u,v ，求 u 和 v 之间的最短路径长度。如果 u 无法到达 v ，输出 -1。

输入描述:

本题要求强制在线。

第一行给出两个整数 n,Q \; (1 \leq n \leq 10^5, 1 \leq Q \leq 2 \times 10^5)，n 表示无向图的点的数量，Q 表示操作的次数。

接下来有 Q 行,每行给出 3 个正整数 A,B,C(1 \leq A ,B,C < 998244353)。具体意义如下：

假设 lastans 为上一次 2 操作的答案。定义一开始时 lastans =0。
\begin{aligned}<br /><br />&opt =1+(((A×(2+lastans)) \bmod 998244353)\bmod 2)\\<br />&u =1+(((B×(2+lastans)) \bmod 998244353)\bmod n) \\ <br />&v =1+(((C×(2+lastans)) \bmod 998244353)\bmod n)<br />\end{aligned}

其中 opt 表示操作的种类， u,v 的具体意义如题意所示。

输出描述:

对于每次询问，输出一行整数表示答案。
示例1

输入

复制 
5 7
2 499122184 13
1 13 499122190
499122186 10 499122185
249561091 748683266 499122178
665496237 332748123 4
332748119 2 6
665496241 332748121 332748122

输出

复制 
2
1
1
2

说明

原本的样例数据为
5 7
1 1 2
1 2 3
2 1 3
2 1 2
2 2 3
1 2 4
2 1 4