Fagurkeradvergurinn er ekki óþekktur listunnandi. Í húsi sínu á hann stórt safn málverka. Uppáhaldsmálverkið hans sýnir net með 10 hnútum sem lítur svona út:

Skýringarmynd af úttakinu í fyrsta dæminu.

Dag einn, á meðan hann dáðist að uppáhaldsmálverkinu sínu, áttaði dvergurinn sig á því hvaða eiginleikar gera þetta net svona frábært: það er samanhangandi, hver hnútur hefur nákvæmlega 3 aðlæga leggi, og netið inniheldur engar rásir af lengd 4 (það er að segja, það eru engir fjórir leggir $(v_1, v_2)$, $(v_2, v_3)$, $(v_3, v_4)$ og $(v_4, v_1)$ fyrir neitt mengi fjögurra ólíkra hnúta $v_1, v_2, v_3, v_4$).

Lostinn yfir þessari uppgötvun velti Fagurkeradvergurinn fyrir sér hvort til væru önnur net með þessa eiginleika. Þar sem hann vill verða stór karl í listaheiminum hefur hann aðeins áhuga á stórum netum, nánar tiltekið þeim sem hafa að minnsta kosti 42 hnúta (42 virðist einhvern veginn vera töff tala í hans augum).

Hjálpaðu dvergnum: fyrir gefinn fjölda hnúta skaltu búa til óstefnt einfalt net (án snara eða margfaldra leggja milli sama hnútapars) með þessa eiginleika, eða ákvarða að ekkert slíkt net sé til.

Inntak

Fyrsta og eina lína inntaksins inniheldur eina heiltölu $N$, fjölda hnúta.

Úttak

Ef engin lausn er til skaltu prenta NO.

Annars skaltu prenta eina heiltölu $M$ í fyrstu línunni, fjölda leggja í netinu.

Hver af næstu $M$ línum á að innihalda tvær heiltölur $a_i$ og $b_i$ ($1 \le a_i, b_i \le N$), sem tákna endapunkta leggs.

Ef til eru margar gildar lausnir máttu prenta hverja sem er þeirra.

Takmarkanir

$42 \le N \le 10^6$.

Dæmi

Inntak 1

10

Úttak 1

15
1 2
2 3
3 4
4 5
5 1
1 6
2 7
3 8
4 9
5 10
6 8
8 10
10 7
7 9
9 6

Inntak 2

8

Úttak 2

NO

Athugasemd

Athugið: dæmin hér að ofan uppfylla ekki skilyrðið $N \ge 42$, svo þú þarft ekki að standast þau. Sýnidæmið í dómarakerfinu hefur $N = 42$.