eolymp
Problems

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

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

Группа молодых учёных в одной развивающейся стране решила построить атомный реактор для получения оружейного плутония. Вам, как компьютерному гению этой группы, поручили разработать систему охлаждения реактора.

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

prb2093

У каждой трубы имеется пропускная способность cij. Кроме того, для обеспечения достаточного охлаждения требуется, чтобы по трубе протекало не менее lij единиц жидкости за единицу времени. То есть для трубы, ведущей из i-го узла в j-ый должно выполняться lijfijcij.

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

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

Первая строка входного файла содержит числа N и M – количество узлов и труб (1N200). Следующие M строк содержат описание труб. Каждая строка содержит четыре целых числа i, j, lij и cij. Любые два узла соединены не более чем одной трубой, если есть труба из i в j, то нет трубы из j в i, никакой узел не соединен трубой сам с собой, 0lijcij105.

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

Если решение существует, выведите на первой строке выходного файла слово YES. Затем выведите M чисел – количество жидкости, которое должно течь по трубам, числа должны быть выведены в том порядке, в котором трубы заданы во входном файле. Если решения не существует, выведите NO.

Time limit 2 seconds
Memory limit 64 MiB
Input example #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
Output example #1
NO