#!/usr/bin/env python3
"""Exact, finite simple undirected minimum cycle bases; writes JSON to stdout only."""
from dataclasses import dataclass
from fractions import Fraction
from heapq import heappush, heappop
import itertools
import json


def check(ok, message):
    if not ok:
        raise ValueError(message)


def integer(x):
    return type(x) is int


@dataclass(frozen=True)
class Graph:
    n: int
    edges: tuple
    adj: tuple

    @classmethod
    def make(cls, n, edges):
        check(integer(n) and n >= 0, 'nonnegative integer vertex count')
        rows = []
        ids, pairs = set(), set()
        for row in edges:
            check(type(row) in (tuple, list) and len(row) == 4, 'edge (id,u,v,w)')
            eid, u, v, weight = row
            check(integer(eid) and eid not in ids, 'distinct integer edge IDs')
            check(integer(u) and integer(v) and 0 <= u < n and 0 <= v < n, 'vertex')
            check(u != v and (min(u,v), max(u,v)) not in pairs, 'simple graph')
            check(type(weight) in (int, Fraction) and weight >= 0, 'exact nonnegative weight')
            ids.add(eid); pairs.add((min(u,v), max(u,v)))
            rows.append((eid, min(u,v), max(u,v), Fraction(weight)))
        rows.sort()
        adj = [[] for _ in range(n)]
        for e, (_, u, v, _) in enumerate(rows):
            adj[u].append((v,e)); adj[v].append((u,e))
        return cls(n, tuple(rows), tuple(tuple(x) for x in adj))


def indices(mask):
    while mask:
        bit = mask & -mask
        yield bit.bit_length()-1
        mask ^= bit


def valid_mask(g, mask):
    check(integer(mask) and 0 <= mask < (1 << len(g.edges)), 'edge mask')


def parity(a,b):
    return (a & b).bit_count() & 1


def weight(g, mask):
    return sum((g.edges[e][3] for e in indices(mask)), Fraction(0))


def edge_ids(g, mask):
    return [g.edges[e][0] for e in indices(mask)]


def cycle_vertices(g, mask):
    """Validate and canonically orient a nonempty simple cycle mask."""
    valid_mask(g, mask)
    adjacency = {}
    for e in indices(mask):
        _,u,v,_ = g.edges[e]
        adjacency.setdefault(u,[]).append((v,e))
        adjacency.setdefault(v,[]).append((u,e))
    check(len(adjacency) >= 3 and all(len(x)==2 for x in adjacency.values()), 'cycle degrees')
    start = min(adjacency); path = [start]; used = set(); u = start
    while True:
        choices = [(v,e) for v,e in adjacency[u] if e not in used]
        check(bool(choices), 'closed cycle')
        v,e = min(choices); used.add(e); path.append(v); u = v
        if u == start:
            break
        check(len(used) <= len(adjacency), 'cycle traversal')
    check(len(used) == mask.bit_count(), 'one connected cycle')
    return path


def forest(g):
    """Fixed ID-ordered spanning forest, using component relabeling."""
    labels = list(range(g.n)); chosen = 0
    for e,(_,u,v,_) in enumerate(g.edges):
        if labels[u] != labels[v]:
            old, new = labels[v], labels[u]
            labels = [new if x == old else x for x in labels]
            chosen |= 1 << e
    components = len(set(labels))
    return chosen, [e for e in range(len(g.edges)) if not (chosen >> e)&1], components


def dijkstra(g, start, support=None):
    """Pair weights (w,2**edge_rank); support=None is the original graph."""
    if support is not None:
        valid_mask(g, support)
    size = g.n if support is None else 2*g.n
    check(integer(start) and 0 <= start < size, 'source')
    dist = [None]*size; parent = [None]*size; order = []
    dist[start] = (Fraction(0),0); heap = [(Fraction(0),0,start)]
    while heap:
        a,b,u = heappop(heap)
        if dist[u] != (a,b):
            continue
        order.append(u)
        v0,bit = (u,0) if support is None else divmod(u,2)
        for v,e in g.adj[v0]:
            target = v if support is None else 2*v+(bit ^ ((support >> e)&1))
            cost = (a+g.edges[e][3], b+(1 << e))
            if dist[target] is None or cost < dist[target]:
                dist[target] = cost; parent[target] = (u,e)
                heappush(heap, (*cost,target))
    return dist, parent, order


def tree_masks(g, parent, order, root):
    masks = [None]*g.n; masks[root] = 0
    for v in order:
        if v != root:
            u,e = parent[v]
            masks[v] = masks[u] ^ (1 << e)
    return masks


def reduce_mask(mask, pivots):
    residual = mask
    while residual:
        p = residual.bit_length()-1
        if p not in pivots:
            break
        residual ^= pivots[p]
    return residual


def greedy(g, candidates, rank):
    pivots = {}; basis = []; steps = []
    for mask in sorted(set(candidates), key=lambda x:(weight(g,x),x)):
        residual = reduce_mask(mask,pivots)
        steps.append({'cycle':mask,'residual':residual,'accepted':bool(residual)})
        if residual:
            pivots[residual.bit_length()-1] = residual
            basis.append(mask)
    check(len(basis)==rank, 'candidate set spans cycle space')
    return basis, steps


def fundamental_basis(g, forest_mask, chords):
    adj = [[] for _ in range(g.n)]
    for e in indices(forest_mask):
        _,u,v,_ = g.edges[e]; adj[u].append((v,e));adj[v].append((u,e))
    masks = [None]*g.n
    for root in range(g.n):
        if masks[root] is not None:continue
        masks[root]=0; stack=[root]
        while stack:
            u=stack.pop()
            for v,e in adj[u]:
                if masks[v] is None:masks[v]=masks[u]^(1<<e);stack.append(v)
    return [masks[g.edges[e][1]]^masks[g.edges[e][2]]^(1<<e) for e in chords]


def horton(g):
    tree,chords,c = forest(g); r=len(chords)
    candidates={}
    if r:
        for root in range(g.n):
            _,parents,order = dijkstra(g,root)
            paths=tree_masks(g,parents,order,root)
            for e,(_,u,v,_) in enumerate(g.edges):
                if paths[u] is None:continue
                mask=paths[u]^paths[v]^(1<<e)
                if mask:candidates.setdefault(mask,(root,e))
    basis,steps=greedy(g,candidates,r)
    return {'forest':tree,'chords':chords,'components':c,'rank':r,
            'candidates':candidates,'basis':basis,'steps':steps}


def extract_odd_cycle(g, vertices, edge_order, support):
    """Extract an odd simple closed segment; repeated original vertices allowed."""
    valid_mask(g,support)
    check(len(vertices)==len(edge_order)+1 and bool(vertices) and vertices[0]==vertices[-1], 'closed walk')
    total_parity=0
    for i,e in enumerate(edge_order):
        check(integer(e) and 0 <= e < len(g.edges),'edge rank')
        u,v=vertices[i:i+2]; check(integer(u) and integer(v),'walk vertices')
        check({u,v}==set(g.edges[e][1:3]),'walk incidence')
        total_parity ^= (support >> e)&1
    check(total_parity==1,'odd walk')
    stack_v=[vertices[0]];stack_e=[];pos={vertices[0]:0}
    for e,v in zip(edge_order,vertices[1:]):
        stack_e.append(e)
        if v not in pos:
            pos[v]=len(stack_v);stack_v.append(v);continue
        cut=pos[v]; segment=stack_e[cut:]; odd=0
        for f in segment:odd^=(support >> f)&1
        if odd:
            mask=0
            for f in segment:mask^=1<<f
            cycle_vertices(g,mask)
            return mask
        for z in stack_v[cut+1:]:del pos[z]
        del stack_v[cut+1:];del stack_e[cut:]
    raise ValueError('odd walk must contain an odd simple cycle')


def odd_cycle(g, support):
    valid_mask(g,support)
    best=None; all_dist=[]
    for v in range(g.n):
        dist,parent,_=dijkstra(g,2*v,support); d=dist[2*v+1];all_dist.append(d)
        if d is not None and (best is None or (d,v)<(best[0],best[1])):
            states=[2*v+1];edges=[];u=2*v+1
            while u != 2*v:
                u,e=parent[u];states.append(u);edges.append(e)
            states.reverse();edges.reverse();best=(d,v,states,edges)
    if best is None:return None
    d,v,states,edges=best
    mask=extract_odd_cycle(g,[x//2 for x in states],edges,support)
    check(parity(mask,support)==1 and (weight(g,mask),mask)<=d,'extraction cost')
    return {'cycle':mask,'root':v,'states':states,'walk_edges':edges,'distance':d,'all_distances':all_dist}


def de_pina(g):
    tree,chords,c=forest(g); supports=[1<<e for e in chords];basis=[];steps=[]
    for i in range(len(chords)):
        s=supports[i];found=odd_cycle(g,s);check(found is not None,'valid chord support has an odd cycle')
        cycle=found['cycle']; updates=[]
        for j in range(i+1,len(supports)):
            if parity(cycle,supports[j]):
                before=supports[j];supports[j]^=s;updates.append((j,before,supports[j]))
        basis.append(cycle);steps.append({'support':s,'oracle':found,'updates':updates})
    return {'forest':tree,'chords':chords,'components':c,'rank':len(chords),'basis':basis,'steps':steps}


def describe(g,mask):
    return {'mask':mask,'edges':edge_ids(g,mask),'weight':str(weight(g,mask)),'vertices':cycle_vertices(g,mask)}


def enumerate_cycles(g):
    out=[]
    for mask in range(1,1<<len(g.edges)):
        try:cycle_vertices(g,mask)
        except ValueError:continue
        out.append(mask)
    return out


def main():
    g=Graph.make(5,[(10,0,1,1),(20,1,2,1),(30,2,3,1),(40,3,0,1),
                    (50,0,4,2),(60,1,4,1),(70,2,4,1),(80,3,4,2)])
    h=horton(g);d=de_pina(g);fund=fundamental_basis(g,h['forest'],h['chords'])
    exact,_=greedy(g,enumerate_cycles(g),h['rank'])
    optimum=sum((weight(g,x) for x in exact),Fraction(0))
    for got in (h,d):check(sum((weight(g,x) for x in got['basis']),Fraction(0))==optimum,'main optimum')
    migrations=[]
    for n,rows in [(0,[]),(3,[]),(5,[(7,0,1,0),(19,1,2,0),(31,2,0,0),(90,3,4,2)]),
                   (4,[(7,0,1,1),(19,1,2,1),(31,2,0,1),(90,2,3,2)])]:
        x=Graph.make(n,rows);a=horton(x);b=de_pina(x);check(a['basis']==b['basis'] or sum(weight(x,c)for c in a['basis'])==sum(weight(x,c)for c in b['basis']),'migration optimum')
        migrations.append({'n':n,'rank':a['rank'],'components':a['components'],'basis':[describe(x,c)for c in a['basis']]})
    x=Graph.make(4,[(7,0,1,1),(19,1,2,1),(31,2,0,1),(90,2,3,2)])
    check(odd_cycle(x,1<<3) is None,'bridge support NONE')
    walk=[3,2,0,1,2,3];walk_edges=[3,2,0,1,3]
    extracted=extract_odd_cycle(x,walk,walk_edges,1)
    bad=[lambda:Graph.make(True,[]),lambda:Graph.make(-1,[]),lambda:Graph.make(1,[(1,0,0,0)]),
         lambda:Graph.make(2,[(1,0,1,-1)]),lambda:Graph.make(2,[(1,0,1,0.5)]),
         lambda:Graph.make(2,[(1,0,1,True)]),lambda:Graph.make(2,[(True,0,1,1)]),
         lambda:Graph.make(2,[(1,True,0,1)]),lambda:Graph.make(2,[(1,0,2,1)]),
         lambda:Graph.make(3,[(1,0,1,1),(1,1,2,1)]),lambda:Graph.make(2,[(1,0,1,1),(2,1,0,2)]),
         lambda:odd_cycle(x,True),lambda:odd_cycle(x,16),lambda:extract_odd_cycle(x,[0,1,0],[0,0],1)]
    for f in bad:
        try:f()
        except ValueError:continue
        raise ValueError('illegal input accepted')
    return {'edges':[[eid,u,v,str(w)]for eid,u,v,w in g.edges],'rank':h['rank'],
            'forest':edge_ids(g,h['forest']),'chords':[g.edges[e][0]for e in h['chords']],
            'fundamental':[describe(g,z)for z in fund],'fundamental_total':str(sum(weight(g,z)for z in fund)),
            'horton_candidates':[dict(describe(g,z),root=h['candidates'][z][0],extra_edge=g.edges[h['candidates'][z][1]][0]) for z in sorted(h['candidates'],key=lambda z:(weight(g,z),z))],
            'horton_basis':[describe(g,z)for z in h['basis']],'horton_steps':h['steps'],
            'de_pina_basis':[describe(g,z)for z in d['basis']],'de_pina_steps':d['steps'],
            'optimum':str(optimum),'all_simple_cycles':len(enumerate_cycles(g)),
            'migrations':migrations,'bridge_support':None,'closed_walk':walk,
            'closed_walk_weight':str(sum(x.edges[e][3]for e in walk_edges)),
            'extracted':describe(x,extracted),'invalid_rejections':len(bad)}


if __name__=='__main__':
    print(json.dumps(main(),ensure_ascii=False,indent=2,default=lambda x:str(x) if isinstance(x,Fraction)else x))