Циркуляція#5446
Назвемо циркуляцією потік із сумарною величиною . Задано орієнтований граф, в якому для кожного ребра вказано нижню та верхню пропускні здатності. Для кожного напрямленого ребра з вершини до вершини позначимо потік f_{ij}, нижню межу l_{ij}, верхню межу c_{ij}. Потік по ребру повинен задовольняти нерівності l_{ij} \leq f_{ij} \leq c_{ij} для всіх ребер.
Потрібно визначити, чи існує у цьому графі циркуляція, яка задовольняє всі ці обмеження.
У першому рядку вхідних даних зазначено два цілих числа і (1 \leq N \leq 200, 0 \leq M \leq 15000) — кількість вершин і ребер відповідно. Далі йдуть рядків, кожен з яких описує ребро графа. У кожному рядку чотири цілих числа: , , l_{ij}, c_{ij} (1 \leq i, j \leq N, 0 \leq l_{ij} \leq c_{ij} \leq 10^5), тобто з вершини проведено ребро до вершини з нижньою межею l_{ij} та верхньою межею c_{ij}. Гарантується, що якщо існує ребро з до , то з до ребра немає.
Якщо не існує допустимої циркуляції, виведіть NO. Інакше у першому рядку виведіть YES. У наступних рядках виведіть значення потоку через кожне ребро (у порядку, як у вхідних даних). Для кожного ребра з до потік f_{ij} повинен задовольняти l_{ij} \leq f_{ij} \leq c_{ij}.
Приклад 1