Дан неориентированный граф, в котором каждое ребро покрашено либо в чёрный цвет, либо в красный цвет.
Ваша задача присвоить каждой вершине по вещественному числу таким образом, что:
- сумма чисел на обеих концах каждого чёрного ребра равна \(1\);
- сумма чисел на обеих концах каждого красного ребра равна \(2\);
- сумма модулей всех присвоенных чисел наименьшая возможная.
Если это не возможно, выведите, что не существует такого комплекта чисел.
Выходные данные
Если решение существует, выведите в первой строке слово «YES» и во второй строке выведите \(N\) чисел. Для каждого \(i\) (\(1 \le i \le N\)), \(i\)-е из этих чисел должно равняться числу, присвоенному вершине с номером \(i\).
Вывод должен соответствовать следующим ограничениям точности:
- сумма чисел на концах каждого ребра должна отличаться от нужной суммы для этого ребра меньше, чем на \(10^{-6}\);
- сумма модулей всех присвоенных чисел отличается от наименьшего возможного меньше, чем на \(10^{-6}\).
Если существует несколько решений, выведите любое из них.
Если решения не существует, выведите одно слово «NO».
Система оценки
Подзадачи:
- (5 баллов) \(N \leq 5\), \(M \leq 14\)
- (12 баллов) \(N \leq 100\)
- (17 баллов) \(N \leq 1000\)
- (24 баллов) \(N \leq 10\,000\)
- (42 баллов) Без дополнительных ограничений.
Примечание
Примите во внимание, что во втором примере решение не уникальное.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 4
1 2 1
2 3 2
1 3 2
3 4 1
|
YES
0.5 0.5 1.5 -0.5
|
|
2
|
2 1
1 2 1
|
YES
0.3 0.7
|
|
3
|
3 2
1 2 2
2 3 2
|
YES
0 2 0
|
|
4
|
3 4
1 2 2
2 2 1
2 1 1
1 2 2
|
NO
|