eolymp
bolt
Try our new interface for solving problems
Problems

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

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

Time limit 2 seconds
Memory limit 64 MiB

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

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

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

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

Input data

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

Output data

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

Examples

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