E - Верный Editorial /

Time Limit: 6 sec / Memory Limit: 512 MB

問題文

IOI2015の開催されたアルマトイは昔、Верный(ヴェールヌイ)という名前であった。
どうやらロシア語で「忠実な」とか「信頼できる」とかいった意味があるらしい。。
joisinoお姉ちゃんは、これを聞いて、部下が自分にいかに忠実かを試そうとした。

まず、木Xと木Yを用意した。各頂点は0から(木の頂点数-1)までの名前がついており、'a'から'j'までのどれかの小文字のアルファベットが一つ書かれている。

以下の操作をQ回行う。

  • AからBまでの木X上のパス(A,B含む)上にあるアルファベット2つを入れ替える。
    　　例えば、'a'と'b'を入れ替えると、パス上の'a'は'b'となり、'b'は'a'となる。
  • AからBまでの木Y上のパス(A,B含む)上にあるアルファベット2つを入れ替える。
    　　例えば、'a'と'b'を入れ替えると、パス上の'a'は'b'となり、'b'は'a'となる。
  • 木XのAからBまでのパス(A,B含む)上にあるアルファベットを並べた文字列と、木YのCからDまでのパス(C,D含む)上にあるアルファベットを並べた文字列が完全に一致するか、そうでないかを答える。
  • a回のクエリを実行した直後の状態に戻す。
    　 ただし、(このクエリを処理する前に処理したクエリの数)≧a≧0とする。

    • 制限

    1≦Q≦10^5
    1≦(木Xの頂点数)≦10^5
    1≦(木Yの頂点数)≦10^5

    配点

    • この問題に部分点は存在しない。すべてのテストケースに正解すると100点が得られる。

    入力

    入力は以下の形式で標準入力から与えられる。

    木Xについてのデータ
木Yについてのデータ
Q
クエリ1
クエリ2
.
.
.
クエリQ
    　始めに、木Xについてのデータが与えられる。
    　その次に、木Yについてのデータが与えられる。
    　その次に、クエリ数を指す整数Qが1行で与えられる。 　その次のQ行は各クエリを意味する。
    　各木のデータは、以下の形式で与えられる。
    N
s
a_1 b_1
a_2 b_2
.
.
.
a_N-1 b_N-1
    　データ内の1行目に、木の頂点数Nが整数で与えられる。
    　次の1行に、長さNの文字列sが与えられる。この文字列のi+1文字目(0≦i＜N)は、木の頂点iに書かれている小文字を指す。
    　次のN-1行の各行は、木の辺を意味する。
    　a_iとb_iは、頂点a_iと頂点b_i(0＜i≦N-1)の間に辺があることを意味する。

    　各クエリは1行から与えられる。 　まず、初めにクエリの種類を指す整数tが与えられる。 　
      　
    • tが0の時
      　空白区切りでこの後に整数a,bと小文字c,dがこの順で与えられる。 　これは、木Xの頂点a,b間のパス上の頂点(a,b含む)それぞれにおいて、cが書かれている場合dに、dが書かれている場合cに書き換えることを意味する。 　
      • 　
    • tが1の時
      　空白区切りでこの後に整数a,bと小文字c,dがこの順で与えられる。 　これは、木Yの頂点a,b間のパス上の頂点(a,b含む)それぞれにおいて、cが書かれている場合dに、dが書かれている場合cに書き換えることを意味する。 　
      • 　
    • tが2の時
      　空白区切りでこの後に整数a,bと小文字c,dがこの順で与えられる。 　これは、(木Xの頂点a,b間のパス上の頂点(a,b含む)に書かれている文字を、aから順に並べたときの文字列)と(木Yの頂点c,d間のパス上の頂点(c,d含む)に書かれている文字を、cから順に並べたときの文字列)が一致するかしないかを答えることを意味する。 　
      • 　
    • tが3の時
      　空白区切りでこの後に整数aが与えられる。 　これは、木Xと木Yを、a回クエリを処理した直後の状況に戻すことを意味する。 　

    出力

    　それぞれのクエリにおいてtが2のとき、文字列が一致する場合"YES"、一致しない場合"NO"を1行に出力せよ。
    　なお入力全体の最後には改行を忘れないこと。

    入力例1

    4
ckdl
0 2
0 1
1 3
4
lckd
2 1
1 3
2 0
4
2 2 3 3 0
2 2 3 0 3
2 3 2 0 3
2 3 2 3 0

    出力例1

    YES
NO
YES
NO