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