Since the entire graph is always a forest, we can claim the following property about question queries:

• If \(u\) and \(v\) belong to different connected components, there is no conforming vertex.
• If \(u\) and \(v\) belong to the same connected component:
  • regard the connected component as a tree rooted at an arbitrary vertex;
  • then, if there is a conforming vertex \(w\), then at least one of these holds: “\(w\) is the parent of \(u\)” or “\(w\) is the parent of \(v\).”

If you are allowed to solve the problem offline, we can prefetch the queries, take an arbitrary root for each of the final connected components, find the parent for each vertex, and inspect at most two candidate vertices (whether edge \(u-w\) or edge \(v-w\) exists at the point of the question query) to solve the problem.

However, we can hardly prefetch the queries as they are encrypted. How can we solve it online?

We exploit the trick called “square-root decomposition of queries.**

• Divide the queries into blocks, each of size \(B\).
• Before processing each block, process all the queries so far, spending about \(O(N)\) time.
• For each block, apply the updates by the queries in it, spending about \(O(B)\) time.
• As a result, the total time complexity will be \(O(\frac{NQ}{B} + BQ)\). Picking \(B=\sqrt{N}\), we can achieve \(O(Q \sqrt{N})\).

When starting to process a block

Construct a forest according to the edges added so far. Just as before, take an arbitrary root for each of the resulting connected components to find the parent of each vertex.
Also, for this graph \(G_i\) we have obtained, check the connected component that each vertex belongs to.

When processing the block

On edge addition, just memorized that an edge was added.

On an question, inspect \(G_i\) constructed right before this block is processed. There are two possible cases:

• If \(u\) and \(v\) belong to the same connected component on \(G_i\):
  • Just as before, the sought vertex is either the parent of \(u\) or the parent of \(v\).
• If \(u\) and \(v\) belong to different connected components on \(G_i\):
  • If there exists a conforming vertex \(w\), then either edge \(u-w\) or edge \(v-w\) must be added within the block. There are at most \(B\) edges in the block.

By implementing above, this problem can be solved in a total of \(O(Q \sqrt{N})\) time. (However, natural implementation may have additional \(\log\). If you are not careful in implementation, you might need to tune \(B\) to speed it up.)

Sample code (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;
}