Kim 博士は古代アマゾン王国の遺跡を探索中、女王の家系図を 2 つ発見しました。各家系図には、最初の女王 1 人とその女性の子孫の親子関係が、以下のような木として記録されています。例えば図 1 では $C$ が最初の女王で、$F$ と $D$ は $C$ の子です。同じ人の子の間に順序はありません。

図 1

発見時、2 つの家系図には、次のように定義する単位損傷が 0 回以上起きていたことが分かりました。

単位損傷：親 $P$ とその子 $Q$ が 1 人に合併されます。両者の子すべて（$Q$ を除く）は、合併後の人の子になります。

例えば図 2 で $A$ と $F$ を合併する単位損傷が起きると図 3 になります。さらに図 3 で $B$ と $D$ を合併する単位損傷（図 4）が起きると図 5 になります。

図 2

図 3

図 4

図 5

図 5 で $E$ と $G$ を合併する単位損傷（図 6）が起きると図 7 になります。

図 6

図 7

幸い、子のいない人（図で数字の名前を持つ人）を含む単位損傷は起きていません。また、子のいない人の名前はすべて家系図に残っており、互いに異なります。しかし、子のいる人（図で英字の名前を持つ人）の名前は 1 つも残っていません。そのため、発見された家系図は図 8 のようになります。

図 8

同じ原本でも単位損傷の起こり方によって異なる結果が得られます。ただし、図 9 の 2 つの家系図は同じ原本からは作れません。

図 9

入力された 2 つの家系図が、同じ原本から 0 回以上の単位損傷で作れるか判定するプログラムを作成してください。入力の家系図 $S$ と $T$ では、子のいない人の名前の集合は同じです。つまり、$S$ の子のいない人の名前を集めた集合と、$T$ の対応する集合は等しいです。

ソースファイル名は family.c または family.cpp を推奨しますが、別の名前でもサーバーに提出できます。

入力

標準入力から次の情報が与えられます。最初の行には最初の家系図の人数 $N_1$、2 番目の人数 $N_2$、各家系図の子のいない人数 $K$ が与えられます。最初の家系図では人に $1$ から $N_1$、2 番目では $1$ から $N_2$ の番号が付いています。両方とも $1$ から $K$ の人には子がなく、同じ番号の人は同じ名前です。

次の行に、最初の家系図の各人の親の番号が本人の番号順に与えられます。親がいない場合は $0$ です。続く行には 2 番目の家系図の各人の親の番号が同じ順序で与えられ、親がいない場合は $0$ です。

出力

標準出力に、2 つの家系図を同じ原本から作れるなら YES、不可能なら NO を、英大文字で出力してください。

小課題

すべての小課題で $1 \le K < N_1,N_2$ です。

• 1: 17/100 点; $2 \le N_1,N_2 \le 300$. 最初の家系図には単位損傷が起きていません。
• 2: 27/100 点; $2 \le N_1,N_2 \le 300$.
• 3: 15/100 点; $2 \le N_1,N_2 \le 5\,000$.
• 4: 41/100 点; $2 \le N_1,N_2 \le 300\,000$.

入出力例

入力 1

3 3 2
3 3 0
3 3 0

出力 1

YES

入力 2

5 5 3
4 4 5 5 0
4 5 5 0 4

出力 2

NO

入力 3

7 8 4
7 7 6 6 0 5 5
6 7 7 8 0 5 5 5

出力 3

NO