Задача №113703. Раскраска графа
Дан граф из \(n\) вершин, раскрасьте его в минимально возможное число цветов так, чтобы никакие две вершины, соединенные ребром, не были одного цвета.
В первой строке содержится число \(t\) - количество тестовых примеров (\(1 \leq t \leq 5\)).
Далее содержится \(t\) тестовых случаев, заданных в следующем формате:
В первой строке записаны числа \(n\) и \(m\) - количество вершин и ребер соответственно (\(1 \leq n \leq 17\), \(0 \leq m \leq \frac{n \cdot (n - 1)}{2}\)).
Затем идет \(m\) строк, в которых содержится по два числа \(v_i\) \(u_i\), что означает, что вершины \(v_i\) и \(u_i\) соеденены ребром (\(1 \leq v_i, u_i \leq n, v_i \neq u_i\)).
Гарантируется, что все ребра в каждом тестовом случае различны.
Для каждого тестового случая в первой строке выведите минимальное число цветов \(k\).
Во второй строке выведите \(n\) чисел \(a_i\) - цвета вершин (\(1 \leq a_i \leq k\)).
3 3 3 1 2 2 3 3 1 5 3 2 1 3 1 4 2 6 7 1 2 1 5 2 5 2 3 2 4 5 6 5 4
3 3 2 1 2 1 2 2 1 1 3 1 3 1 1 2 1