与えられる文字列は関係なく、最終的にどの文字がどの文字に変わるかを追えばよいです。
そこで、次のような問題を解くことを考えます。

長さ \(\sigma\) の数列 \(A\) が与えられる。
最初、 \(A_i = i\) である。
各クエリでは \(a, b\) が与えられるので、 \(A_i = a\) なる全ての \(i\) に対して \(A_i = b\) に変更せよ。

この問題は次のような解法で解くことができます。

• 最初に \(\sigma\) 個の頂点を作成し、 \(i\) 個目の頂点には \((0, i)\) を書き込んでおく。
  また、長さ \(\sigma\) の数列 \(T\) を作成し、全ての要素を \(0\) とする。
• \(i\) 個目のクエリで \(a_i, b_i\) が与えられたとする。
  この時、 \(a_i = b_i\) ならば何もしない。
  \(a_i \neq b_i\) ならば、 \((T_{a_i}, a_i)\) と \((T_{b_i}, b_i)\) を連結にする。
  その後、新たに \((i, a_i)\) が書かれた頂点を追加して、 \(T_{a_i} = i\) とする。
• 最終的に、\(A\) の \(i\) 番目の要素は \((0, A_i)\) と連結な頂点のうち第一要素が最大の頂点に書かれた値の第二要素と一致する。

この解法が何をしているかを説明します。

まず、ここで作成している頂点は (クエリを何個捌いたか, 書いてある値) を管理していると考えます。
すると、\(i\) 番目のクエリでは有向辺として \((i-1, a_i) \rightarrow (i, b_i)\) を繋ぎ、 \(a_i\) 以外の頂点では \((i-1, v) \rightarrow (i, v)\) を繋ぎたいです。 ここで変化点は \(a_i\) だけなので、変化があった部分だけを管理する方針を取ると、数列 \(T\) を持つことで \(1\) 本の辺だけ繋げば良くなります。

また、このグラフは枝分かれすることがありません。
従って、最終的な行き先を求めるだけならば無向辺として考えても良いことが分かります。
従って、この問題はグラフに何度か辺を貼り、その後に連結成分に対する要素を求める問題となりました。
これはDSUを使えば解ける問題となっているので、高速に解くことができます。

計算量は \(O(\sum_{i=1}^N |S_i| + \sigma + Q\alpha(\sigma + Q))\) で、文字の種類数が増えても高速に解くことができます。
もちろんDFSやBFSを用いて \(O(\sum_{i=1}^N |S_i| + \sigma + Q)\) で解いても構いません。