元のグラフを \(G\) とします。頂点は正方形状に並んでいると考え、頂点 \((i,\ j)\) を \(i\) 行 \(j\) 列目に存在する頂点とします。

\((i,\ j) \rightarrow (i-j,\ j)\) と座標変換すると各クエリは整数 \(u_i,\ v_i,\ p_i\) に対し \((u_i,\ k),\ (v_i,\ k+p_i)\) 間に辺を張るというものになります。また、整数列 \(h=(h_1,\ h_2,\ \dots,\ h_N)\) に対し \((i,\ j) \rightarrow (i,\ j+h_i)\) という座標変換を施してもクエリの形は保たれます（各行を何列かずらしてもよいということです）。

以下を満たすように \(h\) を取ります。

• \(i\) 番目のクエリ \((u_i,\ v_i,\ p_i)\)で辺を追加する直前において、どの \(0 \le j,\ j' < N\) に対しても \((u_i,\ j),\ (v_i,\ j')\) が連結でないとき、 \(p_i=0\)

この条件は、上記のようなクエリの \((u_i,\ v_i)\) に対して \(h_{u_i}-h_{v_i}=p'_i\) という条件になります。 \(N\) 頂点で \((u_i,\ v_i)\) 間に辺を持つグラフは森になるのでこのような \(h\) は必ず存在します。

さらに上記のようなもの以外のクエリ \((u_i,\ v_i,\ p_i)\) については、辺を追加する直前において \((u_i,\ k)\) と \((v_i,\ k)\) が連結なので、クエリは \((u_i,\ k),\ (u_i,\ k+p_i)\) 間に辺を張るというものと考えることができます。

以上をまとめると適切な \(h\) を取ることでクエリは

• \((u_i,\ k),\ (v_i,\ k)\) 間に辺を追加するクエリ
• \((u_i,\ k),\ (u_i,\ k+p_i)\) 間に辺を追加するクエリ

の \(2\) 種類になります。

まず \(1\) 種類目のクエリだけを行うと \(G\) を \(1\) 列目だけに制限したグラフ \(G_{row}\) が各列に並びます。さらにつづけて \(2\) 種類目のクエリを行うと \(G_{row}\) の各連結成分に対する \(N\) 列が \(g\ (=\) \(2\) 種類目のクエリの \(p_i\) のうち関係するもの、および \(N\) の最大公約数 \()\) 列ごとに連結されます。

よってクエリを処理する際は \(h\) を \(1\) つ定めた後、

• \(1\) 列目にできているグラフ \(G_{row}\)
• \(G_{row}\) の各連結成分が何列ごとに連結になっているかを管理する数列 \(g\)

を適切に管理、更新すればクエリが処理できます。これは dsu などを利用することで \(O((N+Q)\log N)\) でできます。