"""Authored unit-capacity augmentations with real reverse-edge cancellation."""
import itertools,json

def run(reverse=True):
    nodes=['S','A','B','T'];caps={('S','A'):1,('S','B'):1,('A','B'):1,('A','T'):1,('B','T'):1}
    flow={e:0 for e in caps};trace=[]
    def remaining(u,v):
        return caps.get((u,v),0)-flow.get((u,v),0)+(flow.get((v,u),0) if reverse else 0)
    def dfs(u,seen):
        if u=='T':return [u]
        for v in nodes:
            if v not in seen and remaining(u,v)>0:
                path=dfs(v,seen|{v})
                if path:return [u]+path
        return None
    def check():
        assert all(0<=flow[e]<=caps[e] for e in caps)
        for u in ['A','B']:assert sum(f for (a,b),f in flow.items()if b==u)==sum(f for (a,b),f in flow.items()if a==u)
    while True:
        path=dfs('S',{'S'})
        if path is None:break
        bottleneck=min(remaining(u,v)for u,v in zip(path,path[1:]));steps=[]
        for u,v in zip(path,path[1:]):
            if (u,v)in caps:flow[u,v]+=bottleneck;kind='increase_original'
            else:flow[v,u]-=bottleneck;kind='cancel_previous_original'
            steps.append({'from':u,'to':v,'kind':kind,'amount':bottleneck})
        check();trace.append({'path':path,'changes':steps,'flow':{'->'.join(e):f for e,f in flow.items()}})
    value=sum(f for (u,v),f in flow.items()if u=='S')
    cuts=[]
    for flags in itertools.product([0,1],repeat=2):
        left={'S'}|{u for u,b in zip(['A','B'],flags)if b}
        cuts.append({'source_side':sorted(left),'capacity':sum(c for (u,v),c in caps.items()if u in left and v not in left)})
    return {'capacities':{'->'.join(e):c for e,c in caps.items()},'augmentations':trace,'value':value,'final_flow':{'->'.join(e):f for e,f in flow.items()},'independent_all_four_cuts':cuts,'minimum_cut_capacity':min(x['capacity']for x in cuts)}

def demo():
    good=run(True);bad=run(False)
    assert good['value']==good['minimum_cut_capacity']==2 and bad['value']==1
    assert good['augmentations'][0]['path']==['S','A','B','T'] and good['augmentations'][1]['path']==['S','B','A','T']
    assert good['final_flow']['A->B']==0 and good['augmentations'][1]['changes'][1]['kind']=='cancel_previous_original'
    return {'authored_dfs_augmenting_flow':good,'incorrect_no_reverse_residual':bad,'edmonds_karp_networkx_or_real_capacity_executed':False}

if __name__=='__main__':print(json.dumps(demo(),indent=2))