Система отопления в доме состоит из n узлов и m двунаправленных труб, соединяющих пары узлов. Система устроена таким образом, что горячая вода циркулирует по трубам и объем воды, втекающей в каждый узел (в единицу времени) равен объему воды, вытекающей из узла. Это верно для всех узлов, кроме двух специальных: истока (имеет исходящий поток) и стока (имеет входящий поток). Все остальные узлы удовлетворяют условию, что объем воды, втекающей в узел, равен объему воды, вытекающей из узла.
Каждая труба характеризуется двумя параметрами: пропускной способностью и коэффициентом трения. Пропускная способность i-й трубы обозначается как ci и означает максимальный объем воды, который может протекать по этой трубе в единицу времени. Вода может течь по трубе в любом из двух направлений. Коэффициент трения i-й трубы обозначается как pi. Трение в i-й трубе зависит от pi и от объема текущего через нее потока воды fi следующим образом: трение равно pi·fi2.
Известно, что вода протекает через систему отопления таким образом, что суммарный поток воды максимален. Это означает, что объем воды, проходящий через систему в единицу времени, максимален. Среди всех способов, удовлетворяющих этому критерию, поток воды протекает через систему таким образом, что сумма величин трения по всем трубам минимальна.
Напишите программу, которая находит такой максимальный поток, что суммарное трение минимально.
Входные данные состоят из нескольких тестовых наборов. каждый тестовый набор начинается со строки, содержащей два целых числа n и m (2 ≤ n ≤ 50, 1 ≤ m ≤ 100). Каждая из последующих m строк содержит по четыре целых числа xi, yi, ci и pi (1 ≤ xi, yi ≤ n; xi ≠ yi; 1 ≤ ci, pi ≤ 50), где xi и yi это номера узлов, соединенных i-й трубой, а ci и pi это пропускная способность и коэффициент трения i-й трубы. Между парой узлов не может быть более одной трубы. Узлы нумеруются числами от 1 до n.
Первый узел является истоком, последний – стоком. Гарантируется, что сток достижим из истока по трубам.
Для каждого тестового набора, выведите его номер, максимальную величину потока и минимальное суммарное трение. Величины потока и трения выводите не менее, чем с 3 знаками после десятичной точки. Затем выведите значения f1, f2, ..., fm потоков через трубы с номерами 1, 2, ..., m. Положительные значения fi соответствуют направлению потока от xi к yi, а отрицательные — обратному направлению. Каждое значение fi выводите не менее, чем с 9 знаками после десятичной точки.
5 5
2 1 1 1
2 3 1 1
1 4 1 1
4 3 1 1
3 5 1 1
3 1
1 3 13 17
Case 1: 1.0000000000 2.0000000000
-0.5000000000 0.5000000000 0.5000000000 0.5000000000 1.0000000000
Case 2: 13.0000000000 2873.0000000000
13.0000000000
