Tutkiessaan Uolevin DNA:ta tutkijat löysivät myös kaksi erikoista molekyyliä. Kummassakin molekyylissä on n atomia, joista yksi on uraaniatomi ja muut ovat happiatomeita. Lisäksi atomien välillä on n-1 sidosta ja kaikki atomit ovat jotain kautta yhteydessä toisiinsa.

Tutkijat eivät päässeet kuitenkaan selvyyteen, onko kyseessä kaksi aidosti erilaista molekyyliä, vai onko niiden rakenne samanlainen. Molekyylien rakenne on samanlainen, jos ne näyttävät piirrettynä samoilta, kunhan atomien sijainnit valitaan sopivasti. Voisitko auttaa tutkijoita?

Syöte

Syötteen ensimmäisellä rivillä on kokonaisluku n: atomien määrä molekyylissä. Atomit on numeroitu kokonaisluvuin 1,2,\ldots,n, ja atomi 1 on uraani.

Sitten syötteessä on n-1 riviä, jotka kuvaavat ensimmäisen molekyylin. Jokaisella rivillä on kaksi kokonaislukua a ja b: kaksi atomia, joiden välillä on sidos molekyylissä.

Lopuksi syötteessä on n-1 riviä, jotka kuvaavat toisen molekyylin vastaavalla tavalla.

Tuloste

Ohjelmasi tulee tulostaa YAY, jos molekyylit ovat samanlaiset, ja muuten QAQ.

Rajat

• 2\leq n\leq 3\cdot 10^4

Esimerkki

Syöte:

5
1 2
1 3
3 4
3 5
1 2
1 3
2 4
2 5

Tuloste:

YAY