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