クエリの操作を愚直にシミュレーションする方法では、すべてのクエリの処理を行うために最悪で \(\mathrm{\Theta}(QN)\) 時間かかり、実行制限時間に間に合わせることは絶望的です。
そこで、ある定数 \(B\) を定め、\(N\) 個の頂点を「次数が \(B\) 以上の頂点からなるグループ」と「次数が \(B\) 未満の頂点からなるグループ」に分け、グループごとに異なる取り扱いをする方針によって高速化をはかります。

入力で与えられる順にクエリを見ていきます。 \(i = 1, 2, \ldots, Q\) について、\(i\) 番目のクエリでは下記の手順1から手順3を行います。

手順1: 頂点 \(x_i\) に現在書かれている整数を正しい値に書き換える（後述）。
手順2: 頂点 \(x_i\) に書かれている”正しい”値を \(X\) とおく。
手順3: 頂点 \(x_i\) の次数が \(B\) 以上であるかそうでないかに応じて、以下の (a) または (b) を行う。

(a) 頂点 \(x_i\) の次数が \(B\) 未満である場合

頂点 \(x_i\) に隣接するすべての頂点について、そこに書かれた整数を \(X\) に書き換えます。 このとき「書き換えたのがクエリ \(i\) である」こともそれぞれの頂点に記録しておきます。
この処理にかかる時間は、頂点 \(x_i\) の次数が \(B\) 未満であることから、\(\mathrm{O}(B)\) です。

(b) 頂点 \(x_i\) の次数が \(B\) 以上である場合

頂点 \(x_i\) に隣接するすべての頂点の整数を書き換える代わりに、「この頂点に隣接するすべての頂点の整数が、クエリ \(i\) によって \(X\) に書き換えられた」ことを表す看板を頂点 \(x_i\) に立てます。 過去のクエリによって頂点 \(x_i\) にすでに看板が立てられていた場合は、古い看板は撤去し最新の看板のみを残します。
看板の設置・撤去は、実装上は変数に対する値の変更として \(\mathrm{O}(1)\) 時間で実現できます。

手順1: 「頂点 \(x_i\) に現在書かれている整数を正しい値に書き換える」について

上記の (b) の処理では、本来書き換えるべき頂点を書き換えずに看板を立てて済ませています。 そのため、手順1の直前の時点で頂点 \(x_i\) に現在書かれている整数は本来書かれているべき整数とは異なっている可能性があります。 そのため手順1で、頂点 \(x_i\) に隣接するすべての「次数が \(B\) 以上の頂点」に立てられた看板を確認し、頂点 \(x_i\) に書かれた整数に対する最新の更新を反映する必要があります。
この処理にかかる時間は、次数が \(B\) 以上の頂点は高々 \(2M/B\) 個しかないことから、\(\mathrm{O}(M/B)\) です。

上記の方法によって、すべてのクエリの処理を \(\mathrm{O}(Q(B+M/B))\) 時間で行うことができます。 \(B\) の値を \(\sqrt{M}\) 程度に設定することで、すべてのクエリの処理を \(\mathrm{O}(Q\sqrt{M})\) 時間で行うことができ、\(\mathrm{O}(N+M+Q\sqrt{M})\) 時間でこの問題を解くことができます。

すべてのクエリを処理したあと各頂点に書かれた整数を出力する際にも、各頂点に書かれている正しい整数を手順1の要領で復元する必要があることに注意して下さい。