Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

A. Граф
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дан неориентированный граф, в котором каждое ребро покрашено либо в чёрный цвет, либо в красный цвет.

Ваша задача присвоить каждой вершине по вещественному числу таким образом, что:

  • сумма чисел на обеих концах каждого чёрного ребра равна $$$1$$$;
  • сумма чисел на обеих концах каждого красного ребра равна $$$2$$$;
  • сумма модулей всех присвоенных чисел наименьшая возможная.

Если это не возможно, выведите, что не существует такого комплекта чисел.

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

Первая строка содержит два целых числа $$$N$$$ ($$$1 \leq N \leq 100\,000$$$) и $$$M$$$ ($$$0 \leq M \leq 200\,000$$$): количество вершин и рёбер, соответственно. Вершины пронумерованы последовательными числами $$$1, 2, \ldots, N$$$.

Следующие $$$M$$$ строк содержат описание рёбер. Каждая строка содержит три целых числа $$$a$$$, $$$b$$$ и $$$c$$$, которые обозначают, что между вершинами $$$a$$$ и $$$b$$$ ($$$1 \leq a, b \leq N$$$) есть ребро цвета $$$c$$$ ($$$1$$$ обозначает чёрное, $$$2$$$ обозначает красное).

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

Если решение существует, выведите в первой строке слово «YES» и во второй строке выведите $$$N$$$ чисел. Для каждого $$$i$$$ ($$$1 \le i \le N$$$), $$$i$$$-е из этих чисел должно равняться числу, присвоенному вершине с номером $$$i$$$.

Вывод должен соответствовать следующим ограничениям точности:

  • сумма чисел на концах каждого ребра должна отличаться от нужной суммы для этого ребра меньше, чем на $$$10^{-6}$$$;
  • сумма модулей всех присвоенных чисел отличается от наименьшего возможного меньше, чем на $$$10^{-6}$$$.

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

Если решения не существует, выведите одно слово «NO».

Система оценки

Подзадачи:

  1. (5 баллов) $$$N \leq 5$$$, $$$M \leq 14$$$
  2. (12 баллов) $$$N \leq 100$$$
  3. (17 баллов) $$$N \leq 1000$$$
  4. (24 баллов) $$$N \leq 10\,000$$$
  5. (42 баллов) Без дополнительных ограничений.
Примеры
Входные данные
4 4
1 2 1
2 3 2
1 3 2
3 4 1
Выходные данные
YES
0.5 0.5 1.5 -0.5
Входные данные
2 1
1 2 1
Выходные данные
YES
0.3 0.7
Входные данные
3 2
1 2 2
2 3 2
Выходные данные
YES
0 2 0
Входные данные
3 4
1 2 2
2 2 1
2 1 1
1 2 2
Выходные данные
NO
Примечание

Примите во внимание, что во втором примере решение не уникальное.