1765. Which Pipes Are Worth Widening

A DIRECTED network has n junctions and m pipes, pipe i running from u to v with capacity c. For EACH pipe, in the order it was listed, print Yes if raising that one pipe's capacity by exactly 1 would raise the maximum flow from s to t, and No if it would not.

Print None when m is 0, so the output is never an empty line.

1->2 cap 1, 2->3 cap 1 s=1 t=3 pipe 1 -> No pipe 2 -> No

Widening either pipe alone changes nothing, because the other one still caps the flow at 1. Both have to be widened together, so neither qualifies on its own. That is the shape of this problem: being FULL is not the same as being worth widening.

1->2 cap 1, 2->3 cap 2, 1->3 cap 1 s=1 t=3 pipe 1 (1->2) -> Yes pipe 2 (2->3) -> No pipe 3 (1->3) -> Yes

The flow is 2 and the only bottleneck is the pair of pipes leaving junction 1. Widening either of those lets a third unit through, because 2->3 still has one unit of slack. Widening 2->3 itself changes nothing, since junction 1 cannot release any more.

## What most people try first

Answer Yes for every pipe that the finished flow fills to capacity. The first example above refutes it: both pipes are full and both answers are No.

The second attempt is to recompute the whole flow m times, once per widened pipe. It is correct, it is the definition, and it is what this problem's oracle does on networks of at most six junctions. At n = 100 and m = 500 it is m flows of O(n * m * m), about 1.25 * 10^10 steps.

## The method, one flow and two searches

Run the maximum flow once. In the FINAL residual network, compute two sets:

A = the junctions reachable FROM s (a forward search) B = the junctions that can REACH t (a backward search)

Then pipe i from u to v answers Yes exactly when u is in A and v is in B.

Running the backward search is the only fiddly part. The arcs INTO a junction y are the partners of the arcs in y's own list: for each arc e listed at y, the arc e ^ 1 runs into y, so y is reachable backwards from the far end of e when e ^ 1 still has capacity.

## Why that test is exactly right

Give pipe i one more unit of capacity. The residual network gains one unit on the arc u -> v and loses nothing. A larger flow exists if and only if some augmenting route from s to t now exists.

If u is in A and v is in B, then s reaches u, the new unit carries the route from u to v, and v reaches t: a route exists, so the flow rises, and it rises by at least 1.

If not, then every route in the enlarged residual network still has to use the new unit at some point, since the network without it had no route at all. But using it means arriving at u from s and leaving v for t, which is precisely u in A and v in B. So no route exists and the flow does not move.

Notice this also explains the first example. Both pipes are full, but after the flow, A = {1} and B = {3}, so pipe 1->2 fails on v = 2 not being in B and pipe 2->3 fails on u = 2 not being in A.

## Cost

One flow at O(n * m * m) plus two searches at O(n + m), so about 2.5 * 10^7 at n = 100 and m = 500. The flow total needs 64 bits, since 500 pipes of 10^9 reach 5 * 10^11 and a signed 32-bit integer stops at 2147483647; the output is only Yes and No.

Constraints - `2 ≤ n ≤ 100` - `0 ≤ m ≤ 500` - `1 ≤ u, v ≤ n` - `1 ≤ c ≤ 1000000000` - `1 ≤ s, t ≤ n` and `s ≠ t`, so `n` is never 1 - self-loops and parallel pipes can occur, and both `u` to `v` and `v` to `u` may be present - the network may be disconnected, in which case every answer is `No`