E - Верный

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回のクエリを実行した直後の状態に戻す。
      ただし、(このクエリを処理する前に処理したクエリの数)≧a0とする。

  • 制限

    1Q10^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文字目(0iN)は、木の頂点iに書かれている小文字を指す。
     次のN-1行の各行は、木の辺を意味する。
     a_ib_iは、頂点a_iと頂点b_i(0iN-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