E. Капитализм
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Общество может быть представлено как связный, неориентированный граф с $$$n$$$ вершинами и $$$m$$$ ребрами. Вершины соответствуют людям, а ребро $$$(i,j)$$$ обозначает дружбу между людьми $$$i$$$ и $$$j$$$.

В этом обществе доход $$$i$$$-о человека равен $$$a_i$$$. Человек $$$i$$$ завидует человеку $$$j$$$, если $$$a_j=a_i+1$$$. То есть человек $$$j$$$ имеет ровно на $$$1$$$ больше дохода, чем человек $$$i$$$.

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

Неравенство доходов общества определяется как $$$\max\limits_{1 \leq i \leq n} a_i - \min\limits_{1 \leq i \leq n} a_i$$$.

Вы знаете про все существующие пары друзей, но не знаете доходы людей. Если это общество не может быть капиталистическим ни при каких доходах людей, сообщите об этом. Иначе, вы должны найти возможные доходы для всех людей такие, чтобы общество было капиталистическим и неравенство доходов было максимальным.

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

В первой строке находится два целых числа $$$n$$$, $$$m$$$ ($$$1\le n\le 200$$$, $$$n-1\le m\le 2000$$$) — количество людей и пар друзей, соответственно.

Следующие $$$m$$$ строк описывают пары друзей. Каждая пара друзей описывается тремя целыми числами $$$i$$$, $$$j$$$, $$$b$$$ ($$$1\le i, j\le n, i\ne j, 0\le b\le 1$$$). Это описание означает, что люди $$$i$$$ и $$$j$$$ друзья. Если $$$b=1$$$, то человек $$$i$$$ завидует человеку $$$j$$$. Если $$$b=0$$$, то один из двух друзей должен завидовать другому, но неизвестно кто именно кому.

Существует не более одной дружбы между любой парой людей. Гарантируется, что если рассмотреть все пары друзей как неориентированные ребра, получившийся граф будет связным.

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

Выведите «YES», если заданное общество может быть капиталистическим и «NO», иначе. Вы можете выводить символы в любом регистре (верхнем или нижнем).

Если ответ «YES» вы должны вывести еще две строки. В первой строке выведите максимальное возможное неравенство доходов. В следующей строке вы должны вывести $$$n$$$ целых чисел $$$a_1,\ldots, a_n$$$ ($$$0\le a_i\le 10^6$$$), где $$$a_i$$$ это доход $$$i$$$-о человека.

Можно доказать, что если решение существует, то существует решение, в котором $$$0\le a_i\le 10^6$$$ для всех $$$i$$$.

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

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

В первом тесте можно показать, что для заданного общества не может быть неравенство доходов, большее чем $$$3$$$. В приведенном ответе с неравенством доходов, равным $$$3$$$:

  • Человек $$$2$$$ завидует человеку $$$1$$$.
  • Человек $$$3$$$ завидует человеку $$$2$$$.
  • Человек $$$5$$$ завидует человеку $$$2$$$.
  • Человек $$$6$$$ завидует человеку $$$5$$$ (удовлетворено условие на то, кто из друзей завидует другому).
  • Человек $$$6$$$ завидует человеку $$$3$$$.
  • Человек $$$2$$$ завидует человеку $$$4$$$ (удовлетворено условие на то, кто из друзей завидует другому).

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