Дистрикты

Как известно, Панем разбит на несколько дистриктов. Дистрикт --- это административно-территориальная единица.

Для проведения Голодных игр из каждого дистрикта выбираются несколько человек.

Наступила пора новых Голодных игр. В них примут участие $n$ человек, каждый из которых проживает в некотором дистрикте. Но произошло непоправимое --- был утерян список, в котором для каждого человека был известен дистрикт, в котором он проживает. Осталась лишь следующая информация: $m$ троек чисел ($x_i, y_i, z_i$) --- каждая тройка означает, что участники с номерами $x_i$, $y_i$ и $z_i$ не проживают в одном дистрикте.

От вас требуется восстановить дистрикты участников, чтобы количество различных дистриктов было минимально.

В первой строке содержатся два целых числа $n, m$ ($1 \le n \le 16$, $0 \le m \le n^3$).

В следующих $m$ строках содержатся тройки различных целых чисел $x_i$ $y_i$ $z_i$, ($1 \le x_i, y_i, z_i \le n$, $x_i \neq y_i, y_i \neq z_i, x_i \neq z_i$).

В первой строке выведите натуральное число $k$ --- минимальное количество различных дистриктов, в которых проживают все участники.

В следующей строке выведите $n$ чисел $a_i$ ($1 \le a_i \le k$) --- номер дистрикта, в котором проживает $i$-й участник. Если существует несколько ответов --- выведите любой.