J. Раскраска графа

Раскрасьте граф в наименьшее возможное число цветов так, чтобы концы каждого ребра были разного цвета. Выведите число цветов и саму раскраску.

Хроматическое число — одна из самых известных NP-трудных величин. При $n \le 16$ она считается за $3^n$.

В первой строке $t$ ($1 \le t \le 3$) — количество тестов. Далее $t$ блоков: в первой строке блока $n$ и $m$ ($1 \le n \le 16$, $0 \le m \le \frac{n(n-1)}{2}$), затем $m$ строк с концами рёбер. Рёбра различны, петель нет.

Для каждого теста выведите в первой строке минимальное число цветов $k$, во второй — $n$ чисел, цвета вершин (каждое от 1 до $k$).

Если раскрасок несколько, выведите любую.