Pamätáš si ešte na intergalaktického zlodeja Okäňa “Bzučiaka” Hruškového?

…

Kým si si pozeral hyperlinky v jeho mene, Okäň “Bzučiak” Hruškový ukradol priamo spod tvojho nosa príbeh tejto úlohy. Neostáva ti nič iné, než vyriešiť nezarozprávkovanú úlohu o bodoch v rovine…

Úloha

V rovine je na celočíselných súradniciach (nie nutne na rôznych) $n$ bodov typu A očíslovaných $0$ až $n-1$ a $n+1$ bodov typu B očíslovaných $0$ až $n$. Bod typu A sa dá aktivovať, čím sa odstráni on, a jemu najbližší bod typu B v euklidovskej vzdialenosti (ak je viacero bodov typu B rovnako vzdialených, vieme si vybrať, ktorý z nich bude odstránený). Rozhodnite, či existuje spôsob, ako každý bod typu A práve raz aktivovať tak, aby jediný bod typu B, ktorý na konci zostane neodstránený, bol ten s číslom $n$, a ak áno, tento postup nájdite.

Formát vstupu

V prvom riadku vstupu je číslo $n$ ($1 \leq n \leq 3000$) udávajúce počet bodov typu A.

Na $i$-tom z ďalších $n$ riadkov sú vždy dve medzerou oddelené celé čísla - súradnice $i$-teho bodu typu A, vždy ležiace v intervale $-10^9$ až $10^9$. Na $i$-tom z ďalších $n+1$ riadkov potom sú opäť dve medzerou oddelené celočíselné súradnice z intervalu $-10^9$ až $10^9$ - súradnice $i$-teho bodu typu B.

V sadách platia nasledujúce obmedzenia:

Formát výstupu

Ak neexistuje spôsob, ako odstrániť všetky body typu B až na $n$-tý, vypíšte na jediný riadok výstupu slovo NIE. Inak vypíšte na prvý riadok výstupu slovo ANO a potom na $n$ nasledujúcich riadkoch konštrukciu riešenia: vždy dve celé medzerou oddelené čísla $0 \leq a,b \leq n-1$ označujúce aktiváciu bodu typu A číslo $a$ a s ním odstránenie bodu typu B číslo $b$. Každý bod typu A musí byť aktivovaný práve raz, a v tom momente nesmie existovať žiaden neodstránený bod typu B, ktorý by k nemu bol bližšie než ten, ktorý ide táto aktivácia odstrániť.

Príklady

4
1 1
1 -1
-1 1
-1 -1
0 0
0 -1
1 0
-1 0
0 1

ANO
0 2
2 3
1 1
3 0

Všetky body sú umiestnené v mriežke 3x3. Najprv odstránime body typu A v dvoch vrchných rohoch (s kladnou y súradnicou), a s nimi body typu B v stredoch ľavej a pravej strany (s nulovou y súradnicou). Potom už len odstránime zvyšné štyri body s nekladnou y súradnicou, a nakoniec zostane iba bod 4, ktorý je na súradniciach (0,1).

5
-1 1
1 1
-1 -1
1 -1
0 1
-1 1
1 1
-1 -1
1 -1
0 -1
0 0

NIE