CF1383F Special Edges

Koa the Koala has a directed graph $ G $ with $ n $ nodes and $ m $ edges. Each edge has a capacity associated with it. Exactly $ k $ edges of the graph, numbered from $ 1 $ to $ k $ , are special, such edges initially have a capacity equal to $ 0 $ . Koa asks you $ q $ queries. In each query she gives you $ k $ integers $ w_1, w_2, \ldots, w_k $ . This means that capacity of the $ i $ -th special edge becomes $ w_i $ (and other capacities remain the same). Koa wonders: what is the [maximum flow](https://en.wikipedia.org/wiki/Maximum_flow_problem#Definition) that goes from node $ 1 $ to node $ n $ after each such query? Help her!

N/A

N/A

For the second sample, the following images correspond to the first two queries (from left to right respectively). For each edge there is a pair flow/capacity denoting flow pushed through the edge and edge's capacity. The special edges are colored in red. As you can see in first query maximum flow from node $ 1 $ to node $ 4 $ equals $ 0 $ and in second query equals $ 1 $ .