グラフ全体が常に森であるため、質問クエリに対して以下の事柄が言えます。

• もし \(u\) と \(v\) が異なる連結成分に属する場合、題意を満たす頂点は存在しない。
• \(u\) と \(v\) が同じ連結成分に属する場合は、以下が成立する。
  • その連結成分中の適当な頂点を根とした木を考える。
  • このとき、題意を満たす頂点 \(w\) が存在すれば、「 \(w\) は \(u\) の親ノード」「 \(w\) は \(v\) の親ノード」の少なくとも一方が満たされる。

もしオフラインで解くことが許されるなら、クエリを先読みした上で最終的な全ての連結成分について適当に根を取って、各ノードについて親ノードを求めた上で、解の候補である高々 \(2\) つのノードが正当であるか ( 辺 \(u-w\), 辺 \(v-w\) が質問クエリの時点で存在するか ) を調べることでこの問題に正解できます。

しかし、クエリが暗号化されているためクエリを先読みして解くことは難しいです。よって、オンラインでこの問題を解くことを考えましょう。

そこで、以下の クエリ平方分割 と呼ばれる技法を活用します。

• クエリをサイズ \(B\) ずつのブロックに分割する。
• 各ブロックを処理し始める際に、これまでのクエリ全体に関して時間計算量 \(O(N)\) 程度の処理をかける。
• 各ブロックの範疇で、そのブロック内で生じた変更をクエリごとの時間計算量 \(O(B)\) 程度で反映させる。
• その結果、全体の時間計算量は \(O(\frac{NQ}{B} + BQ)\) となる。 \(B=\sqrt{N}\) と選択することにより、 \(O(Q \sqrt{N})\) を達成することができる。

各ブロックの処理開始時の処理

それまでに追加された辺に関して森を構成します。そのもとで全ての連結成分について先ほどと同様に適当に根を取って親を求めておきます。
さらに、この時点でのグラフ \(G_i\) について、どの頂点がどの連結成分にあるかも調べておきます。

各ブロック内でのクエリの処理

辺の追加は、単に「この辺を追加した」と記憶しておきます。

質問クエリは、ブロック開始時の \(G_i\) を見て、以下の場合分けを行います。

• \(G_i\) 上で \(u\) と \(v\) とが同一の連結成分にある場合
  • 先ほど同様、題意を満たす頂点は \(u\) の親ノードか \(v\) の親ノードのどちらかです。
• \(G_i\) 上で \(u\) と \(v\) とが異なる連結成分にある場合
  • もし題意を満たす頂点 \(w\) が存在するなら、そのブロック内で \(u-w\) 辺または \(v-w\) 辺が追加されている必要があります。ブロック内の辺は高々 \(B\) 本です。

以上を実装することでこの問題に時間計算量 \(O(Q \sqrt{N})\) で正解できます (が、自然な実装だと \(\log\) が入るので、実装時間に気を遣わなかった場合は \(B\) を調整して高速化する必要があるかもしれません。)

実装例 (C++):

#include<bits/stdc++.h>
#include <atcoder/dsu>
#define mod 998244353

using namespace std;
using namespace atcoder;

using Graph=vector<vector<int>>;

int n,q;
Graph g;
vector<int> genpar(){
  vector<int> vis(n,0);
  vector<int> res(n,-1);
  queue<int> q;
  for(int i=0;i<n;i++){
    if(vis[i]){continue;}
    vis[i]=1;
    q.push(i);
    while(!q.empty()){
      int od=q.front(); q.pop();
      for(auto &nx : g[od]){
        if(vis[nx]==0){
          vis[nx]=1;
          res[nx]=od;
          q.push(nx);
        }
      }
    }
  }
  return res;
}

int b=2000;

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> n >> q;
  g.resize(n);

  vector<int> his={0};
  vector<int> cpar;
  vector<unordered_set<int>> st(n);
  dsu uf(n);
  vector<pair<int,int>> emem;

  for(int tr=0;tr<q;tr++){
    if(tr%b==0){
      cpar=genpar();
      for(auto &nx : emem){
        uf.merge(nx.first,nx.second);
      }
      emem.clear();
    }

    int a,b,c;
    long long ma,mb,mc;
    cin >> ma >> mb >> mc;

    ma*=(his.back()+1); ma%=mod; a=1+(ma%2);
    mb*=(his.back()+1); mb%=mod; b=1+(mb%n);
    mc*=(his.back()+1); mc%=mod; c=1+(mc%n);

    b--;c--;

    if(a==1){
      st[b].insert(c);
      st[c].insert(b);
      g[b].push_back(c);
      g[c].push_back(b);
      emem.push_back({b,c});
    }
    else{
      vector<int> cand;
      if(uf.same(b,c)){
        cand={cpar[b],cpar[c]};
      }
      else{
        for(auto &nx : emem){
          if(nx.first==b || nx.first==c){
            cand.push_back(nx.second);
          }
          if(nx.second==b || nx.second==c){
            cand.push_back(nx.first);
          }
        }
      }

      int oup=-1;
      for(auto &nx : cand){
        if(st[b].find(nx)==st[b].end()){continue;}
        if(st[c].find(nx)==st[c].end()){continue;}
        oup=nx;
      }

      oup++;
      cout << oup << "\n";
      his.push_back(oup);
    }
  }
  return 0;
}