D. Наместничество
ограничение по времени на тест
2 seconds
ограничение по памяти на тест
256 megabytes
ввод
стандартный ввод
вывод
стандартный вывод

В Троичном королевстве ровно n = 3k городов. Все они расположены на побережье реки Триссисипи, которая протекает через все королевство. Некоторые из городов расположены по одну сторону реки, а все остальные — по другую.

Между некоторыми городами построены мосты. Каждый мост соединяет два города, расположенные по разные стороны реки. Между любыми двумя городами имеется не более одного моста.

Недавно взошедший на престол король Тристан Третий занят распределением своих наместников между городами. Всего имеется k наместников и король хочет поручить каждому из них управлять ровно тремя городами. Однако никакому из наместников нельзя поручать управление городами, которые соединены мостом — ради своей выгоды наместник может установить слишком высокую пошлину на проезд по мосту, что плохо скажется на репутации короля.

Помогите королю Тристану Третьему распределить наместников между городами, если это возможно.

Входные данные

В первой строке даны два целых числа n и m — количество городов и мостов (3 ≤ n < 105, n = 3k, 0 ≤ m ≤ 105). В следующих m строках описаны мосты. i-ая строка содержит два целых числа ai и bi — номера городов, которые соединяет i-ый мост (1 ≤ ai, bi ≤ n, ai ≠ bi, 1 ≤ i ≤ m).

Гарантируется, что никакой мост не соединяет город сам с собой, а также, что между любыми двумя городами не более одного моста.

Выходные данные

Если нужным образом распределить наместников нельзя, то в единственной строке выведите «NO» (без кавычек).

Иначе в первой строке выведите «YES» (без кавычек), а во второй — какой наместник должен управлять каждым из городов. i-ое число должно означать номер наместника (от 1 до k), который должен управлять i-ым городом из входных данных — всего n чисел.

Если возможных решений несколько — выведите любое.

Примеры
Входные данные
6 6
1 2
4 1
3 5
6 5
2 6
4 6
Выходные данные
YES
1 2 1 2 2 1
Входные данные
3 1
1 2
Выходные данные
NO