# All Pairs Maximum Flow

“We must respect the other fellow’s religion, but only in the sense and to the extent that we respect his theory that his wife is beautiful and his children smart.” H. L. Mencken Given a square, symmetric matrix of edge capacities, return a square, symmetric matrix of maximum flows. In ther words, you have n nodes. Between each pair of nodes, there is a pipe of a certain thickness (measured in liters per second, possibly zero). For each pair of nodes, (A, B), return the the maximum speed at which fluid can be pushed from node A to node B, in liters per second. Note that the flow for each pair of nodes is maximized separately — there is no need to push all n2 flows simultaneously. Input The first line of input gives the number of cases, N. N test cases follow. Each one starts with a line containing n (0 ≤ n ≤ 200). The next n lines will each contain n integers (between 0 and 10000 (inclusive)). Output For each test case, output one line containing ‘Case #x:’ followed by n lines with n integers each. The diagonal should of this matrix should contain only zeroes. Sample Input 4 2 02 20 6 011010 100101 100100 011000 100001 010010 0 1 0 Sample Output Case #1: 02 20 Case #2: 032222

2/2 302222 220222 222022 222202 222220 Case #3: Case #4: 0