4. Párty žiab

Táto úloha sa dá nahradiť riešením sady loops_cpp na Liahni (betaliahen.ksp.sk) . Ak chceš, aby ti namiesto bodov za riešenie tejto úlohy boli započítané body získané riešením spomínanej sady, na stránke odovdzaj pdf-ko s prezývkou, ktorú používaš na Liahni.

Ak máte akékoľvek otázky ohľadom tejto úlohy, napíšte Paulínke na

Na jazere žijú žaby. Presnejšie, každá žaba žije na svojom lekne. Lekien je na jazere presne \(n\) a na vode plávajú v rade za sebou, očíslované od 1 po \(n\). Každý večer sa v rybníku koná párty žiab. Zorganizovať takúto párty je jednoduché – stačí, keď sa všetky stretnú na tom istom lekne.

Žaby sa však cestou na párty nechcú zamočiť, preto sa na ňu musia dostať iba pomocou skákania po leknách. No a tu to začína byť komplikované. Žiadna žaba nechce byť asociálna a preto musí vždy preskočiť na lekno, na ktorom sedí aspoň jedna ďalšia žaba. A keďže je lekno malé, žaby sa pri skákaní stavajú na seba. Ďalším skákaním sa ich poradie však nemení.

Naviac, keď je na lekne viacero žiab, skáču všetky spoločne. A z neznámych príčin, ak je na lekne \(x\) žiab, tak vedia skočiť iba na lekno, ktoré je vzdialené presne o \(x\) lekien doprava alebo doľava. Na začiatku, keď je žaba na svojom lekne sama, môže skočiť iba na susedné lekno.

Cesta na párty preto vie vyzerať napríklad takto:

Ako si iste viete predstaviť, keď na chrbte niektorej žaby stojí viacero iných žiab, je to pre ňu namáhavé. A námahu veru nemá žaba Michal v láske. Preto by chcel navrhnúť takú postupnosť skokov, aby sa všetky žaby stretli na jednom lekne a on sa ocitol na vrchu kopy. Teda v žiadnom momente nemôže iná žaba (alebo viacero žiab) skočiť na lekno, na ktorom sa nachádza Michal.

Ak by teda v situácii, ktorá je znázornená na obrázku, sedel žaba Michal na štvrtom lekne, tak by mu takáto postupnosť skokov vyhovovala, keďže by nikdy na ňom nestála žiadna iná žaba. Ak by však začínal na druhom lekne, tak v treťom skoku by naňho skočila žaba z lekna štyri, čo by sa mu nepáčilo.

Pomôžte mu nájsť takúto postupnosť skokov!

Úloha

Na vstupe dostaneme počet lekien v rybníku a pozíciu žaby Michala. Nájdite takú postupnosť skokov, že dodržiava všetky vyššie uvedené pravidlá skákania žiab a zároveň platí, že žiadna žaba neskočí na lekno, na ktorom sa nachádza žaba Michal.

Až 9 bodov môžete získať za vyriešenie ľahšej podúlohy, v ktorej sa v rybníku žaba Michal nenachádza. V tom prípade hľadáte iba takú postupnosť skokov, ktorá vedie k tomu, že všetky žaby skončia na tom istom lekne.

Vstup

Na vstupe dostanete dve čísla oddelené medzerou \(n\) a \(m\) určujúce počet lekien a pozíciu žaby Michala.

V niektorých vstupoch bude \(m=-1\). V týchto vstupoch sa žaba Michal nenachádza a teda hľadáme ľubovoľnú postupnosť skokov, po ktorej sa všetky žaby stretnú na tom istom lekne.

Výstup

Ak neexistuje žiadna platná postupnosť ktorá spĺňa podmienky popísané v úlohe, vypíšte "NIE". V opačnom prípade vypíšte "ANO" a následne vypíšte platnú postupnosť skokov. Každý skok je popísaný dvoma číslami \(a\) a \(b\) (\(1 \leq a,b \leq n\)) – všetky žaby z lekna \(a\) skočili na lekno \(b\).

V prípade, že existuje viacero správnych postupností, ktoré vedú k párty žiab, môžete vypísať ľubovoľnú z nich.

Hodnotenie

Váš program bude spustený na piatich sadách vstupných súborov. Body dostanete za každú úspešne vyriešenú sadu. Obmedzenia na veľkosť čísla \(n\) v jednotlivých sadách nájdete v nasledujúcej tabuľke.

Príklady

Input:

5 -1

Output:

ANO
2 3
3 5
4 5
5 1

Tento vstup zodpovedá obrázku v zadaní.

Input:

9 3

Output:

ANO
1 2
3 2
4 5
6 5
7 8
9 8
8 5
2 5