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

Охолодження реактора

Охолодження реактора

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

Група молодих вчених в одній з країн, що розвиваються, вирішила побудувати атомний реактор для отримання збагачаного плутонія. Вам, як комп'ютерному генію цієї групи, доручили розробити систему охолодження реактора.

Система охолодження реактора являє собою набір труб, які з'єднують вузли. По трубам тече рідина, причому для кожної труби строго визначено напрямок, у якому вона повинна по ній текти. Вузли системи охолодження пронумеровані від 1 до N. Система охолодження повинна бути спроектована таким чином, щоб для кожного вузла за одиницю часу кількість рідини, яка втікає у вузол, була рівна кількості рідини, яка витікає з вузла. Тобто якщо з i-го вузла у j-ий тече f_ij одиниць рідини за одиницю часу (якщо з i в j немає труби, то покладемо f_ij = 0), то для кожного вузла i повинно виконуватись:

У кожної труби є пропускна здатність c_ij. Крім того, для забезпечення достатнього охолодження потрібно, щоб по трубі протікало не менше l_ij одиниць рідини за одиницю часу. Тобто для труби, яка веде з i-го вузла у j-ий повинно виконуватись l_ijf_ijc_ij.

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

Вхідні дані

Перший рядок вхідного файлу містить числа N та M – кількість вузлів та труб (1N200). Наступні M рядків містять описи труб. Кожен рядок містить чотири цілих числа i, j, l_ij та c_ij. Довільні два вузли з'єднані не більше ніж однією трубою, якщо є труба з i в j, то немає труби з j в i, ніякий вузол не з'єднано трубою сам з собою, 0l_{ij }≤ c_{ij }≤ 10^5.

Вихідні дані

Якщо розв'язок існує, виведіть у першому рядку вихідного файлу слово YES. Потім виведіть M чисел – кількість рідини, яка повинна протікати по трубам, числа повинні бути виведені у тому порядку, у якому труби задані у вхідному файлі. Якщо розв'зку не існує, виведіть NO.

Приклад

Вхідні дані #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