Дистрикты

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

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

Наступила пора новых Голодных игр. В них примут участие $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$-й участник. Если существует несколько ответов --- выведите любой.