E - Верный

Contest Duration: 2015-10-18(Sun) 04:30 - 2015-10-18(Sun) 09:30 (local time) (300 minutes)

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$ Copy

Copy

出力例 $1$ Copy

Copy

YES
NO
YES
NO

問題文

制限

配点

入力

出力

入力例111Copy

出力例111Copy

入力例 $1$ Copy

出力例 $1$ Copy