AT_ijpc2015_j Верный

[problemUrl]: https://atcoder.jp/contests/ijpc2015/tasks/ijpc2015_j IOI2015の開催されたアルマトイは昔、Верный(ヴェールヌイ)という名前であった。 どうやらロシア語で「忠実な」とか「信頼できる」とかいった意味があるらしい。。 joisinoお姉ちゃんは、これを聞いて、部下が自分にいかに忠実かを試そうとした。 まず、木Xと木Yを用意した。各頂点は$ 0 $から$ (木の頂点数-1) $までの名前がついており、'a'から'j'までのどれかの小文字のアルファベットが一つ書かれている。 以下の操作を$ Q $回行う。 3. $ A $から$ B $までの木X上のパス($ A $,$ B $含む)上にあるアルファベット2つを入れ替える。 例えば、$ 'a' $と$ 'b' $を入れ替えると、パス上の$ 'a' $は$ 'b' $となり、$ 'b' $は$ 'a' $となる。 4. $ A $から$ B $までの木Y上のパス($ A $,$ B $含む)上にあるアルファベット2つを入れ替える。 例えば、$ 'a' $と$ 'b' $を入れ替えると、パス上の$ 'a' $は$ 'b' $となり、$ 'b' $は$ 'a' $となる。 5. 木Xの$ A $から$ B $までのパス($ A $,$ B $含む)上にあるアルファベットを並べた文字列と、木Yの$ C $から$ D $までのパス($ C $,$ D $含む)上にあるアルファベットを並べた文字列が完全に一致するか、そうでないかを答える。 6. $ a $回のクエリを実行した直後の状態に戻す。 ただし、(このクエリを処理する前に処理したクエリの数)≧$ a $≧$ 0 $とする。

入力は以下の形式で標準入力から与えられる。 > 木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 $≦$ Q $≦$ 10^5 $ $ 1 $≦$ (木Xの頂点数) $≦$ 10^5 $ $ 1 $≦$ (木Yの頂点数) $≦$ 10^5 $ ### 配点 - この問題に部分点は存在しない。すべてのテストケースに正解すると$ 100 $点が得られる。