Розфарбування графа#3163
Вам потрібно написати програму, яка шукає оптимальне розфарбування для заданого графа. Кольори застосовуються до вершин графа, і доступні лише два кольори: чорний і білий. Розфарбування графа називається оптимальним, якщо воно максимізує кількість чорних вершин. Розфарбування повинно задовольняти умову, що жодні дві суміжні вершини не можуть бути одночасно чорними.
Малюнок 1: Оптимальне розфарбування графа з трьома чорними вершинами
Граф задається множиною вершин, пронумерованих від до , n \leq 100, і множиною неорієнтованих ребер, які вказані як пари номерів вершин (n_1, n_2), n_1 \neq n_2. Вхідні дані містять графів. У першому рядку задано число . Опис кожного графа починається з рядка, що містить і — кількість вершин і ребер відповідно. Далі йдуть рядків, у кожному з яких описано ребро у вигляді пари номерів вершин, розділених пробілом.
Вихід повинен містити рядків, по два рядки для кожного графа з вхідних даних. Перший з цих двох рядків має містити максимальну кількість вершин, які можна розфарбувати у чорний колір у графі. Другий рядок має містити одне з можливих оптимальних розфарбувань, наведене як список чорних вершин, розділених пробілами.
Приклад 1