Рассмотрим сеть, состоящую из n вершин, пронумерованных от 1 до n. Некоторые пары вершин соединены ребрами. Пара вершин может быть соединена несколькими ребрами, тем не менее, не существует ребра, соединяющего какую-то вершину саму с собой.

Каждое ребро имеет бесконечную пропускную способность (в обоих направлениях), однако в один момент времени ребро может пропускать поток только в одном из направлений. Стоимость пропускания потока по ребру пропорциональна квадрату пропускаемого потока. Точнее, для каждого ребра задана характеристика (вес), стоимость пропускания x потока по ребру с весом w равна w·x².

Известно, что сеть связна (между любой парой вершин есть путь по ребрам). Более того, сеть устроена таким образом, что при удалении любой вершины, она останется связной.

Вам нужно пропустить k (k > 0) потока из вершины 1 в вершину n. Другими словами, вы хотите для каждого ребра выбрать величину (не обязательно целочисленную) и направление, проходящего по этому ребру потока, так, чтобы для вершины 1 значение [сумма всех входящих потоков минус сумма всех выходящих потоков] равнялось  - k, для вершины n это значение равнялась k, а для всех остальных вершин оно равнялось 0.

Желая минимизировать стоимость пропускания k потока, вы нарисовали диаграмму сети и дали задание одному из подчиненных. Недавно, последний сказал, что он нашел оптимальное решение задачи и нарисовал его, но, к сожалению, пролил кофе на рисунок. Поэтому некоторые данные утрачены (вполне возможно, даже части изначальной диаграммы и значение k).

Имея все сохранившиеся данные, вам нужно определить, могло ли решение подчиненного быть оптимальным. Другими словами, определите, существуют ли корректная сеть, значение k (оно должно быть положительным) и оптимальное решение, которые не противоречат никакой сохранившейся информации. Дополнительно, если это возможно, определите эффективность решения подчиненного. Эффективность решения равна суммарной стоимости деленой на k.