Ao explorar as ruínas do antigo reino amazónico, o doutor Kim descobriu duas genealogias de rainhas. Cada uma regista numa árvore as relações entre mães e filhas de uma rainha inicial e das suas descendentes femininas, como abaixo. Por exemplo, na figura 1, $C$ é a rainha inicial, e $F$ e $D$ são filhas de $C$. As filhas de uma pessoa não têm ordem entre si.

Figura 1

Verificou-se que, antes de serem descobertas, as genealogias tinham sofrido zero ou mais danos elementares, definidos a seguir.

Dano elementar: uma mãe $P$ e uma filha sua $Q$ são fundidas numa pessoa. Todas as filhas das duas pessoas, exceto $Q$, passam a ser filhas da pessoa fundida.

Por exemplo, fundir $A$ e $F$ na figura 2 dá a figura 3. Aplicar depois um dano elementar que funde $B$ e $D$ na figura 3 (figura 4) dá a figura 5.

Figura 2

Figura 3

Figura 4

Figura 5

Aplicar um dano elementar que funde $E$ e $G$ na figura 5 (figura 6) dá a figura 7.

Figura 6

Figura 7

Felizmente, nenhum dano elementar envolveu pessoas sem filhas (as de nomes numéricos nas figuras). Todas as pessoas sem filhas mantêm os seus nomes registados e estes são distintos. Porém, nenhum nome das pessoas com filhas (as de nomes alfabéticos) ficou preservado. Assim, as genealogias descobertas têm a forma da figura 8.

Figura 8

Diferentes formas de danificar a mesma genealogia original podem produzir resultados distintos. Contudo, as duas genealogias da figura 9 não podem vir do mesmo original.

Figura 9

Escreva um programa que determine se as duas genealogias dadas podem resultar do mesmo original após zero ou mais danos elementares. Os conjuntos dos nomes de pessoas sem filhas nas genealogias $S$ e $T$ são iguais. Ou seja, o conjunto formado por esses nomes em $S$ é igual ao correspondente conjunto em $T$.

Recomenda-se o nome de ficheiro fonte family.c ou family.cpp, mas pode submetê-lo ao servidor com outro nome.

Entrada

A entrada padrão fornece as informações seguintes. A primeira linha contém o número de pessoas $N_1$ na primeira genealogia, $N_2$ na segunda e o número de pessoas sem filhas $K$ em cada uma. As pessoas são numeradas de $1$ a $N_1$ na primeira e de $1$ a $N_2$ na segunda. Em ambas, as pessoas de $1$ a $K$ não têm filhas, e as pessoas com o mesmo número de $1$ a $K$ têm o mesmo nome.

A linha seguinte dá o número da mãe de cada pessoa na primeira genealogia, por ordem do número da pessoa; se não houver mãe, é dado $0$. A linha seguinte dá da mesma forma os números das mães na segunda genealogia, usando $0$ quando não existe mãe.

Saída

Na saída padrão, apresente YES se as duas genealogias puderem vir do mesmo original, ou NO se for impossível, em letras inglesas maiúsculas.

Subtarefas

Em todas as subtarefas, $1 \le K < N_1,N_2$.

• 1: 17/100 pontos; $2 \le N_1,N_2 \le 300$. A primeira genealogia não sofreu nenhum dano elementar.
• 2: 27/100 pontos; $2 \le N_1,N_2 \le 300$.
• 3: 15/100 pontos; $2 \le N_1,N_2 \le 5\,000$.
• 4: 41/100 pontos; $2 \le N_1,N_2 \le 300\,000$.

Exemplos

Entrada 1

3 3 2
3 3 0
3 3 0

Saída 1

YES

Entrada 2

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

Saída 2

NO

Entrada 3

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

Saída 3

NO