Sukukokouksen jälkeen Uolevin sukulaiset menevät tänä vuonna pizzeriaan. He tilaavat yhden jättipizzan, josta riittää syötävää kaikille. Ongelmana on kuitenkin, että kaikki eivät pidä samoista täytteistä. Lisäksi pizzaan saa valita vain $k$ täytettä.

Ennen pizzan tilausta Uolevi järjesti äänestyksen, jossa sukulaiset pystyivät vaikuttamaan pizzan täytteisiin. Jokainen sukulainen valitsi kaksi eri täytettä jotka hän haluaa pizzaan.

Tehtäväsi on valita pizzaan tasan $k$ täytettä niin, että ainakin yksi jokaisen sukulaisen toiveista toteutuu.

Syöte

Syötteen ensimmäisellä rivillä on luvut $n$, $m$ ja $k$, täytteiden määrä, sukulaisten määrä ja montako täytettä pizzaan saa valita. Sen jälkeen tulee $m$ riviä jotka kertovat mitä täytteitä sukulaiset äänestivät. Rivillä $i$ on kaksi lukua, $a_i$ ja $b_i$ joka tarkoittavat että sukulainen $i$ äänesti täytteitä $a_i$ ja $b_i$.

Tuloste

Tulosta YAY jos on mahdollista valita $k$ täytettä niin, että ainakin yksi jokaisen sukulaisen toiveista toteutuu. Sen jälkeen tulosta $k$ lukua: täytteet jotka valittiin. Jos tämä ei ole mahdollista tulosta QAQ

Rajat

Kaikissa testeissä $a_i \neq b_i$. Lisäksi ei ole ikinä kahta sukulaista jotka äänestävät tasan samoja täytteitä.

Testeissä 1-5

• $4 \le n \le 1000$
• $1 \le m \le 1000$
• $k = 3$

Testeissä 6-10

• $20 \le n \le 1000$
• $1 \le m \le 1000$
• $k = 20$

Testeissä 11-15

• $20 \le n \le 10^5$
• $1 \le m \le 10^5$
• $k = 20$

Testeissä 16-20

• $40 \le n \le 10^5$
• $1 \le m \le 10^5$
• $k = 40$

Esimerkki

Syöte:

8 13 4
1 2
1 4
4 3
3 5
4 5
4 6
6 5
6 7
7 8
8 5
8 2
7 5
4 7

Tuloste:

YAY
2 4 5 7

Syöte:

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

Tuloste:

QAQ