Эстет Ергежейлі — белгілі өнер білгірі. Оның үйінде картиналардың үлкен коллекциясы бар. Оның ең сүйікті картинасында келесідей көрінетін 10 төбесі бар граф бейнеленген:

Бірінші мысалдағы шығыс деректердің иллюстрациясы.

Бір күні өзінің сүйікті картинасына тамсанып тұрып, ергежейлі бұл графты соншалықты керемет ететін қандай қасиеттер екенін түсінді: ол байланысқан, әр төбеге дәл 3 қыр тиісті, және графта ұзындығы 4 болатын циклдер жоқ (яғни, кез келген төрт түрлі $v_1, v_2, v_3, v_4$ төбелер жиыны үшін $(v_1, v_2)$, $(v_2, v_3)$, $(v_3, v_4)$ және $(v_4, v_1)$ төрт қыры бірдей табылмайды).

Бұл жаңалыққа таңғалған Эстет Ергежейлі осындай қасиеттері бар басқа графтар бар ма екен деп ойланды. Ол өнер әлемінде ірі тұлға болғысы келетіндіктен, оны тек үлкен графтар, атап айтқанда кемінде 42 төбесі бар графтар ғана қызықтырады (42 саны оған неге екені белгісіз керемет сан болып көрінеді).

Ергежейліге көмектесіңіз: берілген төбелер саны үшін осы қасиеттері бар бағытталмаған қарапайым графты (ілмектері немесе бір төбелер жұбы арасында еселі қырлары жоқ) құрастырыңыз немесе мұндай графтың жоқ екенін анықтаңыз.

Кіріс деректер

Кіріс деректердің бірінші және жалғыз жолында төбелер санын білдіретін бір бүтін сан $N$ берілген.

Шығыс деректер

Егер шешім болмаса, NO деп шығарыңыз.

Әйтпесе, бірінші жолда графтағы қырлар санын білдіретін бір бүтін сан $M$ шығарыңыз.

Келесі $M$ жолдың әрқайсысында қырдың ұштарын білдіретін екі бүтін сан $a_i$ және $b_i$ ($1 \le a_i, b_i \le N$) болуы керек.

Егер бірнеше дұрыс шешім болса, олардың кез келгенін шығаруға болады.

Шектеулер

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

Мысалдар

Кіріс деректер 1

10

Шығыс деректер 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

Кіріс деректер 2

8

Шығыс деректер 2

NO

Ескертпе

Назар аударыңыз: жоғарыдағы мысалдар $N \ge 42$ шартын қанағаттандырмайды, сондықтан сізден оларды өту талап етілмейді. Тестілеу жүйесіндегі мысалда $N = 42$.