eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Довільна циркуляція

Довільна циркуляція

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

Задано орієнтовну мережу G. Для кожного ребра кріме його пропускної здатності c_i, вказано ще й нижнє обмеження на потік по ребру l_i. Цео означає, що потік по ребру повинен задовільняти нерівності l_{i }f_ic_i.

Циркуляцією у мережі називається довільний потік величини 0. Тобто для циркуляції вірно, що у довільну вершину скільки одиниць потоку втікає, стільки і витікає з неї (у випадку потоку це не вірно для витоку та стоку мережі).

Ваша задача знайти довільну циркуляцію у заданій мережі.

Вхідні дані

У першому рядку записано пару цілих чисел (1n200, 0m400), де n — кількість вершин у мережі, а m — кількість ребер. Далі у m рядках перераховано ребра у форматі from_i, to_i, l_i, c_i, де from_i - це індекс стартової вершини ребра, to_i - це індекс кінцевої вершини ребра, l_i — нижня границя величини потоку по ребру, а c_i — верхня границя (1from_i, to_in, 0l_ic_i10^5). Усі числа — цілі. У графі відсутні кратні ребра та петлі.

Якщо в мережі є ребро з a в b, то у мережі відсутнє ребро з b в a (тобто зустрічних ребер немає).

Вихідні дані

Якщо розв'язку не існує, то виведіть NO. У протилежному випадку виведіть YES. Далі у випадку позитивної відповіді виведіть m рядків. m-ий рядок повинен містити кількість потоку, який протікає по i-й дузі у шуканій циркуляції.

Приклад

Вхідні дані #1
4 6
1 2 1 2
2 3 1 2
3 4 1 2
4 1 1 2
1 3 1 2
4 2 1 2
Вихідні дані #1
NO