Вам потрібно написати програму, яка пробує знайти оптимальне розфарбування для заданого графа. Фарбування застосовується до вершин графа і доступні лише два кольори: чорний та білий. Розфарбування графа називається оптимальним, якшо у ньому максимальна кількість чорних вершин. Розфарбування обмежено тим правилом, що не може бути двох суміжних чорних вершин.
Рисунок 1: оптимальный граф з трьома чорними вершинами
Граф задається множиною вершин, позначенных числами 1...n, n ≤ 100, та набором неорієнтовних ребер, заданих парами чисел – номерами вершин (n_1, n_2), n_1 ≠ n_2. Вхідний файл містить m графів. Число m задано у першому рядку. У першому рядку опису кождого графа містяться числа nіи k, кількість вершин та кількість ребер, відповідно. Наступні k рядків містять ребра - пари номерів вершин, відокремлених пропуском.
Вихідні дані повинні містити 2m рядків, по два рядки для кожного графа, заданого у вхідних даних. Перший рядок повинен містити максимальну кількість вершин графа, які можуть бути пофарбовані у чорний колір. Другий рядок повинен містити одну з можливих оптимальних рохфарбовок. Вона задається списком чорних вершин, відокремлених пропуском.