3-boyama kitabı

Bu tapşırıqda giriş məlumatları yoxdur. Nəzərə alın ki, siz çıxışı çap edən kodu göndərməlisiniz, mətn faylını yox.

Qrafın icazə verilən 3-rənglənməsi, hər bir $n$ zirvəsinə $\{1,2,3\}$ dəstindən rənglərin (rəqəmlərin) təyin olunmasıdır ki, qrafın hər hansı bir $(a,b)$ kənarı üçün zirvələr $a$ və $b$ fərqli rənglərə malik olsun. $n$ zirvəli qraf üçün belə rənglənmələrin sayı $3^n$-dən çox deyil.

Siz qrafın verilmiş sayda 3-rənglənmələri ilə yaradılması üzrə mütəxəssis olmaq istəyən bir şirkətdə işləyirsiniz. Bir gün axşam sizə dəqiq $6k$ 3-rənglənmələri olan qrafın hazırlanması üçün sifariş veriləcəyini öyrənirsiniz. Siz $k$-nın dəqiq dəyərini bilmirsiniz, yalnız $1\le k\le 500$ olduğunu bilirsiniz.

Siz qraf qurmağa başlamaq üçün $k$-nın dəqiq dəyərini gözləmək istəmirsiniz. Əvvəlcədən $19$ zirvədən çox olmayan qraf qurursunuz. Sonra, $k$-nın konkret dəyərini öyrəndikdən sonra, tələb olunan qrafı dəqiq $6k$ 3-rənglənmələri ilə əldə etmək üçün $17$ kənardan çox olmayan əlavə edə bilərsiniz.

Bunu edə bilərsinizmi?

Giriş verilənləri

Giriş məlumatları yoxdur.

Çıxış verilənləri

Əvvəlcə $n$ və $m(1\le n\le 19,1\le m\le n\cdot (n-1)/2)$ — əvvəlcədən qurulmuş qrafın zirvə və kənarlarının sayını çıxarın. Sonra qrafın kənarlarını $(u,v)$ şəklində $m$ sətir çıxarın.

Sonra hər bir $k$ üçün $1$-dən $500$-ə qədər aşağıdakıları yerinə yetirin:

Bu konkret $k$ üçün əlavə edəcəyiniz kənarların sayını $e$ çıxarın $(1\le e\le 17)$. Sonra qrafa əlavə olunacaq kənarları $(u,v)$ şəklində $e$ sətir çıxarın.

Qrafda döngələr olmamalıdır və hər bir $k$ üçün istifadə etdiyiniz bütün $m+e$ kənarları cüt-cüt fərqli olmalıdır. Konkret $k$ üçün qrafın 3-rənglənmələrinin sayı dəqiq $6k$ olmalıdır.

Nümunələr

Nümunədə $k=1,2$ üçün cavab göstərilmişdir.