Context: Find the maximum flow through a directed graph from s to t. Capacities are all integers.

If I'm not mistaken, Edmonds-Karp runs in O(VE²); and if we don't use a BFS but a DFS instead, it runs in O(E*f) where f is the maximum flow (https://en.wikipedia.org/wiki/Maximum_flow_problem) (proofs: https://enos.itcollege.ee/~japoia/algorithms/GT/Introduction_to_algorithms-3rd%20Edition.pdf chapter 26).

I was a bit surprised that Edmonds-Karp wouldn't pass (but I guess it makes sense looking at the constraints) on a cses problem ( https://cses.fi/problemset/task/1694 ). What really surprised me is that the O(E*f) solution passed (https://cses.fi/paste/aba73738dacf15c9ac0337/ even though the capacities can go up to 10^9 so the max flow can definitely go up to 10^9). I'm now trying to hack my own DFS solution, so I tried to hardcore brute force it by generating billions of inputs and seeing if my DFS would time out on one of them: https://pastebin.com/ijUZDn3G. But that ran so fast (within a minute..) without finding any bad cases...

The worst-case example on wikipedia for that O(E*f) (https://en.wikipedia.org/wiki/Ford%E2%80%93Fulkerson_algorithm) doesn't work for a fixed adjacency list. It just shows that if a bad actor could choose what order DFS goes through the graph, then the algorithm could become crazily slow.

I heard there is this test case generator to hack those O(E*f) solutions but I'll be honest, I don't speak Japanese and I'm not advanced enough to figure out what's happening: https://web.archive.org/web/20211009144446/https://min-25.hatenablog.com/entry/2018/03/19/235802

TL;DR: this code passes https://cses.fi/paste/aba73738dacf15c9ac0337/ even though it's O(E*f) and the capacities can go up to 10^9; please hack me.

(EDIT: my comment in the code saying "DFS to find shortest s-t path" is wrong, it's a remnant comment from when I was coding BFS)