"""Original recursive lowlink for simple undirected bridges and cut vertices."""
from itertools import combinations
import json

def validate(nodes,edges,directed=False):
 if directed is not False or type(nodes) is not list or len(nodes)>8 or any(type(x) is not str or not x for x in nodes) or len(set(nodes))!=len(nodes) or type(edges) is not list or any(type(e) is not tuple or len(e)!=2 or e[0] not in nodes or e[1] not in nodes or e[0]==e[1] for e in edges) or len({tuple(sorted(e)) for e in edges})!=len(edges):raise ValueError('simple undirected unique-string graph<=8nodes, known endpoints, no loops or parallel edges')

def cuts(nodes,edges,directed=False):
 validate(nodes,edges,directed);adj={x:[] for x in nodes}
 for u,v in edges:adj[u].append(v);adj[v].append(u)
 disc={};low={};parent={};bridges=[];art=set();trace=[]
 def visit(u):
  disc[u]=low[u]=len(disc);children=0;trace.append({'action':'discover','node':u,'discovery':disc[u],'parent':parent[u]})
  for v in sorted(adj[u]):
   if v==parent[u]:continue
   if v not in disc:
    parent[v]=u;children+=1;visit(v);low[u]=min(low[u],low[v]);bridge=low[v]>disc[u];cut=parent[u] is not None and low[v]>=disc[u]
    if bridge:bridges.append(tuple(sorted((u,v))))
    if cut:art.add(u)
    trace.append({'action':'child_return','parent':u,'child':v,'low_child':low[v],'discovery_parent':disc[u],'bridge':bridge,'nonroot_cut_condition':cut,'low_parent_after':low[u]})
   else:
    low[u]=min(low[u],disc[v]);trace.append({'action':'visited_nonparent_edge','from':u,'to':v,'low_after':low[u]})
  if parent[u] is None:
   if children>1:art.add(u)
   trace.append({'action':'root_rule','node':u,'DFS_children':children,'cut':children>1})
 for u in sorted(nodes):
  if u not in disc:parent[u]=None;visit(u)
 return {'discovery':disc,'low':low,'parent':parent,'bridges':sorted(bridges),'articulation_points':sorted(art),'trace':trace}

def components(nodes,edges):
 # Independent removal oracle: only direct adjacency flood, no discovery/lowlink.
 left=set(nodes);out=[]
 while left:
  seed=min(left);left.remove(seed);found={seed};todo=[seed]
  while todo:
   u=todo.pop();neighbors={v if u==x else x for x,v in edges if u in [x,v]}
   for v in neighbors&left:left.remove(v);found.add(v);todo.append(v)
  out.append(sorted(found))
 return out

def checked(nodes,edges):
 actual=cuts(nodes,edges);baseline=len(components(nodes,edges));bridges=[];art=[]
 for i,e in enumerate(edges):
  if len(components(nodes,edges[:i]+edges[i+1:]))>baseline:bridges.append(tuple(sorted(e)))
 for u in nodes:
  remaining=[x for x in nodes if x!=u];ee=[e for e in edges if u not in e]
  if len(components(remaining,ee))>baseline:art.append(u)
 assert actual['bridges']==sorted(bridges) and actual['articulation_points']==sorted(art)
 return {'nodes':nodes,'edges':edges,'baseline_components':baseline,'algorithm':actual,'independent_removal_bridges':sorted(bridges),'independent_removal_articulation':sorted(art)}

def demo():
 nodes=list('ABCDEFU');edges=[('A','B'),('B','C'),('C','A'),('C','D'),('D','E'),('E','C'),('E','F')];main=checked(nodes,edges);assert main['algorithm']['bridges']==[('E','F')] and main['algorithm']['articulation_points']==['C','E']
 poss=list(combinations('ABCD',2));checks=0
 for mask in range(64):checked(list('ABCD'),[e for i,e in enumerate(poss) if mask&(1<<i)]);checks+=1
 extra=[checked(list('ABCD'),[('A','B'),('A','C'),('A','D')]),checked(list('ABCD'),[('A','B'),('C','D')]),checked([],[])]
 rejected=[]
 for label,nn,ee,d in [('unknown',list('AB'),[('A','X')],False),('parallel',list('AB'),[('A','B'),('B','A')],False),('selfloop',['A'],[('A','A')],False),('directed',list('AB'),[('A','B')],True),('over_budget',list('ABCDEFGHI'),[],False)]:
  try:cuts(nn,ee,d)
  except ValueError:rejected.append(label)
  else:raise AssertionError('expected rejection')
 return {'two_triangles_shared_vertex_plus_tail_and_isolate':main,'all64_four_vertex_simple_graph_removal_oracles':checks,'root_star_disconnected_empty_cases':extra,'invalid_graphs_rejected':rejected,'scope':'original recursive lowlink on simple undirected unweighted graph, not NetworkX run; vendor bridges uses chain decomposition unlike this exercise; parallel edges require edge IDs and are excluded; cut vertex differs from bridge, SCC, MST or real network outage evidence'}
if __name__=='__main__':print(json.dumps(demo(),ensure_ascii=True,indent=2))