3-розфарбовки#10882

3-розфарбовки

1 секунда

128 мегабайтів

Середня

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

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

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

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

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

Вхідні дані

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

Вихідні дані

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

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

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

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

Приклади

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

Приклад 1