Декомпозиция потока
Декомпозиция потока
Задан ориентированный граф, каждое ребро которого обладает целочисленной пропускной способностью. Найдите максимальный поток из вершины с номером 1 в вершину с номером n и постройте декомпозицию этого потока.
Input data
Первая строка содержит количество вершин n и количество ребер m (2 ≤ n ≤ 500, 1 ≤ m ≤ 10000) графа. Следующие m строк содержат по три числа: номера вершин, которые соединяет соответствующее ребро графа и его пропускную способность. Пропускные способности не превосходят 10^9.
Output data
В первую строку количество путей в декомпозиции максимального потока из вершины с номером 1 в вершину с номером n. Следующие строки должны содержать описания элементарых потоков, на который был разбит максимальный. Описание следует выводить в следующем формате: величина потока, количество ребер в пути, вдоль которого течет данный поток и номера ребер в этом пути. Ребра нумеруются с единицы в порядке появления во входных данных.
Examples
4 5 1 2 1 1 3 2 3 2 1 2 4 2 3 4 1
3 1 2 1 4 1 3 2 3 4 1 2 2 5