この問題は 標準形（canonical form） という概念を知っていると解くことが出来る問題です。

(, x, ) からなる文字列 \(S\) の標準形 \(f(S)\) を次のように定義します。

• \(S\) の部分文字列 (xx) を自由に選び xx に置き換える操作を可能な限り繰り返した時に、最終的に得られる文字列。

この時、操作の順番によらず \(f(S)\) は一意に定まります。

(証明) (少し難しいかもしれません, 飛ばしても問題ないです)
帰納法で示します。長さ \(k-1\) 以下の文字列の標準形の一意性を仮定した時に長さ \(k\) の文字列の標準形の一意性を示せればよいです。
長さ \(k\) の文字列 \(S\) に含まれる (xx) が \(m\) 箇所あったとします。明らかに (xx) 同士は disjoint です。\(m=0, 1\) とそれ以外で場合分けします。

• \(m=0\) の場合：\(S\) の標準形は \(S\) 自身です。
• \(m=1\) の場合：\(S\) の標準形は、\(S\) に 1 個しか存在しない (xx) を xx に置き換えたものの標準形と一致します。置き換えた後の \(S\) の長さは \(k-2\) なので帰納法の仮定から \(S\) の標準形の一意性が示されます。
• \(m \geq 2\) の場合：\(S\) に含まれる (xx) を任意に \(2\) 箇所とり a, b と呼ぶことにします。a を xx に置き換える操作は b の存在に影響しない(逆もしかり)ことに注意します。
  今、\(S\) から a を xx に置き換えた文字列 \(S_a\) を考えます。\(S_a\) は長さ \(k-2\) なので、帰納法の仮定から \(S_a\) の標準形は \(S_a\) から b を xx に置き換えた文字列の標準形と一致します。
  一方、\(S\) から b を xx に置き換えた文字列 \(S_b\) を考えます。\(S_b\) は長さ \(k-2\) なので、帰納法の仮定から \(S_b\) の標準形は \(S_b\) から a を xx に置き換えた文字列の標準形と一致します。
  ここで、「\(S_a\) から b を xx に置き換えた文字列」と「\(S_b\) から a を xx に置き換えた文字列」は一致します。よって \(S_a\) の標準形と \(S_b\) の標準形は一致します。 任意の \(a,b\) に対してこの議論は成り立つので、\(S\) からどの (xx) を最初に xx に置き換えても標準形が一意であることが言えました。

以上より証明が完了しました。(証明終わり)

さて、文字列 \(S\) の標準形を一意に定めることができました。この時、次の事実が成り立ちます。

• 次の 2 個の命題は同値である。
  • (1) 文字列 \(A\) に対して問題文で与えられた操作を作用させ続けることで \(A\) を \(B\) と一致させることが出来る。
  • (2) \(f(A) = f(B)\) である。

(証明) (少し難しいかもしれません, 飛ばしても問題ないです)

(2) \(\to\) (1) : \(A\) を \(f(A)\) に変換する操作列 \(v\) と \(B\) を \(f(B)\) に変換する操作列 \(w\) を自由に取ります。
そして、\(A\) を操作列 \(v\) の順に従って \(f(A)\) に変換した後、\(w\) の操作を逆向きに適用する、すなわち xx を (xx) に変換していくことで \(f(A) = f(B)\) を \(B\) に変換することが出来ます。

(1) \(\to\) (2) : 任意の文字列 \(S\) に対して、

• \(S\) の部分文字列 xx を 1 カ所 (xx) に置き換えた文字列を \(S'\) 、
• \(S\) の部分文字列 (xx) を 1 カ所 xx に置き換えた文字列を \(S''\)

とした時、\(S', S''\) が存在すれば \(f(S)=f(S')\), \(f(S)=f(S'')\) が成り立つことが標準形の一意性から従います。よって、操作を作用させる前と後で標準形が変化しないことが言えるので、ここから (1) が成り立つ時に \(f(A) = f(B)\) が成り立ちます。

(証明終わり)

以上の事実から、文字列 \(A, B\) の標準形 \(f(A), f(B)\) を計算できればこの問題が解けることがわかります。

\(f(A)\) の計算は stack などを用いれば計算できます。すなわち、以下のアルゴリズムを動作させれば標準形 \(f(A)\) を得られます。

• 空文字列 \(C\) を用意する。
• \(i=1,2,\dots,|A|\) について次の操作を行う。
  • \(C\) の末尾に \(A_i\) を追加する。
  • \(C\) の末尾 \(4\) 文字が (xx) であれば、xx に置き換える。
• 操作後に得られる文字列 \(C\) が \(f(A)\) である。

このアルゴリズムは \(\mathrm{O}(|A|)\) で動作します。以上より今回の問題を \(\mathrm{O}(|A|+|B|)\) で通すことが出来て、これは十分高速です。

• 実装例(C++)

#include <iostream>
#include <string>
using namespace std;

string canonical_form(const string& S) {
  string T;
  for (auto& c : S) {
    T.push_back(c);
    if ((int)T.size() >= 4 and T.substr(T.size() - 4, 4) == "(xx)") {
      T.erase(end(T) - 4, end(T));
      T += "xx";
    }
  }
  return T;
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  int T;
  cin >> T;
  while (T--) {
    string A, B;
    cin >> A >> B;
    cout << (canonical_form(A) == canonical_form(B) ? "Yes" : "No") << "\n";
  }
}