Вы должны написать программу, которая пытается найти оптимальную раскраску для заданного графа. Цвета применяются к вершинам графа и доступны только два цвета: черный и белый. Раскраска графа называется оптимальной, если в ней максимальное количество чёрных вершин. Раскраска ограничена тем правилом, что не может быть двух смежных чёрных вершин. \includegraphics{https://static.e-olymp.com/content/37/37877d420c9391068ceee575f703d7b0aaf4f65a.jpg} \textit{Рисунок 1}: оптимальный граф с тремя чёрными вершинами \InputFile Граф задаётся множеством вершин, обозначенных числами \textbf{1}...\textbf{n}, \textbf{n} ≤ \textbf{100}, и набором неориентированных рёбер, заданных парами чисел -- номерами вершин (\textbf{n_1}, \textbf{n_2}), \textbf{n_1} ≠ \textbf{n_2}. Входной файл содержит \textbf{m} графов. Число \textbf{m} задано в первой строке. В первой строке описи каждого графа содержатся числа \textbf{n} и \textbf{k}, количество вершин и количество рёбер, соответственно. Следующие \textbf{k} строк содержат рёбра - пары номеров вершин, разделенные пробелом. \OutputFile Выходные данные должны содержать из \textbf{2m} строк, по две строки для каждого графа, заданного во входных данных. Первая строка должна содержать максимальное количество вершин графа, которые могут быть окрашены в чёрный цвет. Вторая строка должна содержать одну из возможных оптимальную раскраску. Она задаётся списком чёрных вершин, разделенных пробелом.