3-розмальовки

У цій задачі немає вхідних даних. Зверніть увагу, що вам слід надіслати код, який виводить результат, а не текстовий файл.

Допустиме 3-розфарбування графа — це таке присвоєння кольорів (чисел) з множини $\{1,2,3\}$ кожній з $n$ вершин, що для будь-якого ребра $(a,b)$ графа вершини $a$ і $b$ мають різні кольори. Для графа з $n$ вершинами таких розфарбувань не більше $3^n$.

Ви працюєте в компанії, яка прагне стати спеціалістом у створенні графів із заданою кількістю 3-розфарбувань. Одного разу ви дізнаєтеся, що ввечері отримаєте замовлення на виготовлення графа з рівно $6k$ 3-розфарбуваннями. Ви не знаєте точного значення $k$, лише те, що $1\le k\le 500$.

Ви не хочете чекати, поки дізнаєтеся точне значення $k$, щоб почати будувати граф. Ви заздалегідь створюєте граф, що містить не більше $19$ вершин. Потім, дізнавшись конкретне значення $k$, ви можете додати не більше $17$ ребер, щоб отримати потрібний граф з рівно $6k$ 3-розфарбуваннями.

Чи зможете ви це зробити?

Вхідні дані

Вхідних даних немає.

Вихідні дані

Спочатку виведіть $n$ і $m(1\le n\le 19,1\le m\le n\cdot (n-1)/2)$ — кількість вершин і ребер початкового графа (побудованого заздалегідь). Потім виведіть $m$ рядків у вигляді $(u,v)$ — ребра графа.

Потім для кожного $k$ від $1$ до $500$ виконайте наступні дії:

Виведіть $e$ — кількість ребер, які ви додасте для цього конкретного $k(1\le e\le 17)$. Потім виведіть $e$ рядків у вигляді $(u,v)$ — ребра, які будуть додані в граф.

У графі не повинно бути петель, і для кожного $k$ всі $m+e$ ребра, які ви використовуєте, повинні бути попарно різними. Кількість 3-розфарбувань графа для конкретного $k$ повинна бути рівно $6k$.

Приклади

У прикладі показано відповідь для $k=1,2$.