Masala N

Uzoq-uzoqlarda bir sayyorada N ta mamlakat mavjud. Bu sayyoradagi ba’zi mamlakatlar o‘rtasida hamkorlik shartnomasi tuzilgan.

Sayyorada iqtisodiy qonun qat’iy:

• Agar ikki mamlakat hamkor bo‘lsa, bir mamlakatning aholisi ikkinchi mamlakatning mahsulotini sotib olsa undan hech qanday boj olinmaydi.
• Agar ikki mamlakat hamkor emas bo‘lsa, bir mamlakatning aholisi ikkinchi mamlakatning mahsulotini sotib olsa undan 500 foiz boj olinadi.

Shu sababdan, agar bir kun kelib barcha mamlakatlar o‘zaro hamkor bo‘lsa, bojlar butunlay yo‘qoladi va sayyora aholisi nihoyatda farovon hayot kechiradi.

Bu sayyorada yashovchi qadimiy Sehrgar o‘zining noodatiy sehr kuchi bilan mamlakatlar o‘rtasidagi hamkorlikni o‘zgartirish qobiliyatiga ega, ya'ni:

• Sehrgar bitta mamlakatni tanlaydi.
• Tanlangan mamlakat bilan ilgari hamkor bo‘lganlarning barchasi endi hamkor emas.
• Aksincha, ilgari hamkor emas bo'lganlarning barchasi endi hamkor bo‘lib qoladi.

Ya’ni, tanlangan mamlakat boshqa barcha mamlakatlarga nisbatan “teskari” holatga o‘tadi.

Savol shuki: Sehrgarning mohirona tanlovlari natijasida, qachondir sayyora aholisi nihoyatda farovon hayot kechiradimi?

Birinchi qatorda bitta butun son N (2 ≤ N ≤ 1000) — mamlakatlar soni.

Masalani osonlashtirish maqsadida mamlakatlar 1 dan N gacha bo'lgan sonlar bilan raqamlangan.

Ikkinchi qatorda bitta butun son M (0 ≤ M < N·(N−1)/2) — hozirgi vaqtda mavjud bo‘lgan hamkorlik shartnomalari soni.

Keyingi M ta qatorda ikkita turli butun son — hamkorlik qilayotgan mamlakatlar raqamlari beriladi.

Agar Sehrgarning mohirona tanlovlari natijasida, qachondir sayyora aholisi nihoyatda farovon hayot kechira olsa HA so'zini, aks holda YO'Q so'zini chop eting.