CF708D Incorrect Flow

At the entrance examination for the magistracy of the MSU Cyber-Mechanics Department Sasha got the question about Ford-Fulkerson algorithm. He knew the topic perfectly as he worked with it many times on programming competition. As the task for the question he was given a network with partially build flow that he had to use in order to demonstrate the workflow of the algorithm. He quickly finished to write the text and took a look at the problem only to understand that the given network is incorrect! Suppose you are given a directed graph $ G(V,E) $ with two special nodes $ s $ and $ t $ called source and sink. We denote as $ n $ the number of nodes in the graph, i.e. $ n=|V| $ and $ m $ stands for the number of directed edges in the graph, i.e. $ m=|E| $ . For the purpose of this problem we always consider node $ 1 $ to be the source and node $ n $ to be the sink. In addition, for each edge of the graph $ e $ we define the capacity function $ c(e) $ and flow function $ f(e) $ . Function $ f(e) $ represents the correct flow if the following conditions are satisfied: 1. For each edge  the flow is non-negative and does not exceed capacity $ c(e) $ , i.e. $ 0

N/A

N/A

In the first sample, the flow is initially correct. Note, that the flow is not maximum, but this is not required. In the second sample, the flow value of the only edge is greater than its capacity. There are two ways to fix this: either increase the capacity up to $ 2 $ or reduce the flow down to $ 1 $ . In the third sample, there is only $ 1 $ unit of flow coming to vertex $ 2 $ , but there are $ 2 $ units going out of it. One of the possible solutions is to reduce the value of the flow on the second edge by $ 1 $ . In the fourth sample, there is isolated circulation of flow, but this description is correct by definition.