次数の大小によって場合分けを行うことでも、この問題を解くことができます。

まず、次のような \(2\) つの解法について考えます。

解法 1

整数の集合 \(\operatorname{neighbor} _ i\ (1\leq i\leq N)\) と整数の組の集合 \(\operatorname{joint} _ i\ (1\leq i\leq N)\) を管理する。

• 辺 \((u,v)\) の追加クエリでは、
  1. すべての \(w\in\operatorname{neighbor} _ u\) に対し、\(\operatorname{joint} _ v\) に \((w,u)\) を、\(\operatorname{joint} _ w\) に \((v,u)\) を追加する。
  2. すべての \(w\in\operatorname{neighbor} _ v\) に対し、\(\operatorname{joint} _ u\) に \((w,v)\) を、\(\operatorname{joint} _ w\) に \((u,v)\) を追加する。
  3. \(\operatorname{neighbor} _ u\) に \(v\) を、\(\operatorname{neighbor} _ v\) に \(u\) を追加する。
• 頂点対 \((u,v)\) に対する質問クエリでは、\(\operatorname{joint} _ u\) に \((v,k)\) の形の要素が含まれているか確認し、含まれているならば \(k\) を回答する。そうでなければ、\(0\) を回答する。

適切な連想配列などを用いることで、質問クエリは \(O(1)\) 時間や \(O(\log N)\) 時間で答えることができます。

しかし、辺の追加クエリでは頂点 \(u,v\) の次数 \(d _ u,d _ v\) に対して \(O(d _ u+d _ v)\) の時間計算量および空間計算量を使い、クエリ全体では最悪 \(O(Q ^ 2)\) となってしまいます。

解法 2

整数の集合 \(\operatorname{neighbor} _ i\ (1\leq i\leq N)\) を管理する。

• 辺 \((u,v)\) の追加クエリでは、\(\operatorname{neighbor} _ u\) に \(v\) を、\(\operatorname{neighbor} _ v\) に \(u\) を追加する。
• 頂点対 \((u,v)\) に対する質問クエリでは、すべての \(1\leq w\leq N\) を探索し、\(u\in\operatorname{neighbor} _ w\) かつ \(v\in\operatorname{neighbor} _ w\) であるような \(w\) が存在すればこれを回答する。存在しなければ、\(0\) を回答する。

この解法も適切な連想配列などを用いることで、辺の追加クエリを \(O(1)\) 時間や \(O(\log N)\) 時間で処理することができます。

しかし、質問クエリでは \(O(N\log N)\) 時間や \(O(N)\) 時間が必要となり、クエリ全体では最悪 \(O(QN\log N)\) 時間や \(O(QN)\) 時間となってしまいます。

ここで、解法 1 と解法 2 を組み合わせることを考えます。

解法1+2

整数の集合 \(\operatorname{neighbor} _ i\ (1\leq i\leq N)\) と整数の組の集合 \(\operatorname{joint} _ i\ (1\leq i\leq N)\) を管理する。 また、整数 \(D\) をひとつ定める。

• 辺 \((u,v)\) の追加クエリでは、
  1. \(\mathbf{|\operatorname{\mathbf{neighbor}} _ u|\leq D}\) ならば、すべての \(w\in\operatorname{neighbor} _ u\) に対し、\(\operatorname{joint} _ v\) に \((w,u)\) を、\(\operatorname{joint} _ w\) に \((v,u)\) を追加する。
  2. \(\mathbf{|\operatorname{\mathbf{neighbor}} _ v|\leq D}\) ならば、すべての \(w\in\operatorname{neighbor} _ v\) に対し、\(\operatorname{joint} _ u\) に \((w,v)\) を、\(\operatorname{joint} _ w\) に \((u,v)\) を追加する。
  3. \(\operatorname{neighbor} _ u\) に \(v\) を、\(\operatorname{neighbor} _ v\) に \(u\) を追加する。
• 頂点対 \((u,v)\) に対する質問クエリでは、\(\operatorname{joint} _ u\) に \((v,k)\) の形の要素が含まれているか確認し、含まれているならば \(k\) を回答する。そうでなければ、\(\mathbf{|\operatorname{\mathbf{neighbor}} _ w|\gt D}\) であるようなすべての \(1\leq w\leq N\) を探索し、\(u\in\operatorname{neighbor} _ w\) かつ \(v\in\operatorname{neighbor} _ w\) であるような \(w\) が存在すればこれを回答する。存在しなければ、\(0\) を回答する。

このように変形し、\(|\operatorname{neighbor} _ w|\gt D\) となるような \(w\) 全体も同様に管理することで、追加クエリの計算時間を \(O(QD)\)（やそれに \(\log\) がつく形）に、質問クエリの計算時間を \(\widetilde O(Q ^ 2/D)\)（やそれに \(\log\) がつく形）にすることができます。

よって、\(D=O(\sqrt Q)\) などととることによって全体の計算時間を \(O(Q\sqrt Q)\)（やそれに \(\log\) がつく形）とすることができます。

最悪空間計算量が \(O(QD)\) となることなどから、\(D\) の値は小さめに取ることで定数倍が良好になります。

#include <iostream>
#include <set>
#include <vector>
#include <map>

int main() {
    using namespace std;
    static constexpr unsigned small_limit{32}, P{998244353};
    unsigned N, Q;
    cin >> N >> Q;
    // 隣接リスト
    vector<set<unsigned>> edges(N);
    // dist2[i][j] := i-v-j なる辺が存在するような v
    vector<map<unsigned, unsigned>> dist2(N);
    // 次数が small_limit より大きい頂点
    vector<unsigned> large_size;

    const auto add_edge{[&edges, &dist2, &large_size](const unsigned from, const unsigned to) {
        // 次数が small_limit を越えるときに large_size に追加
        if (size(edges[from]) == small_limit)
            large_size.emplace_back(from);
        // small_limit 以下なら、dist2 を更新
        if (size(edges[from]) < small_limit)
            for (const auto &e: edges[from])
                dist2[min(to, e)][max(to, e)] = from;
        edges[from].emplace(to);
    }};

    for (unsigned i{}, x{}, A, B, C; i < Q; ++i) {
        cin >> A >> B >> C;
        A = A * (x + 1UL) % P % N;
        B = B * (x + 1UL) % P % N;
        C = C * (x + 1UL) % P % N;
        if (!A) {
            add_edge(B, C); // 辺 B-C を追加：i-B-C なる辺がある i について更新
            add_edge(C, B); // 辺 C-B を追加：B-C-i なる辺がある i について更新
        } else
            cout << (x = [&]() -> unsigned {
                if (dist2[B].contains(C)) // dist2 に情報があればそれを使う
                    return dist2[B][C] + 1;
                // なければ、答えの候補は次数の大きい頂点のどれか
                for (const auto &v: large_size)
                    if (edges[v].contains(B) && edges[v].contains(C))
                        return v + 1;
                return 0;
            }()) << endl;
    }
    return 0;
}