"""Authored tiny undirected minimum spanning forest and subset/path oracles."""
from itertools import combinations
import json,platform
def forest(nodes,edges):
 parent={v:v for v in nodes};chosen=[];trace=[]
 def find(v):
  while parent[v]!=v:v=parent[v]
  return v
 for a,b,w in sorted(edges,key=lambda e:(e[2],min(e[:2]),max(e[:2]))):
  x,y=find(a),find(b);take=x!=y;trace.append({'edge':[a,b,w],'take':take})
  if take:parent[x]=y;chosen.append((a,b,w))
 components=len({find(v) for v in nodes});assert len(chosen)==len(nodes)-components
 return chosen,components,trace
def paths(nodes,edges,start,end):
 adj={v:[] for v in nodes}
 for a,b,w in edges:adj[a].append((b,w));adj[b].append((a,w))
 out=[]
 def walk(v,path,total):
  if v==end:out.append((total,path));return
  for nxt,w in adj[v]:
   if nxt not in path:walk(nxt,path+[nxt],total+w)
 walk(start,[start],0);return out
def demo():
 nodes=list('ABCD');edges=[('A','B',2),('B','C',2),('C','D',2),('A','D',3),('A','C',3)];tree,components,trace=forest(nodes,edges)
 assert components==1 and sum(w for a,b,w in tree)==6
 candidates=[]
 for subset in combinations(edges,3):
  if all(paths(nodes,subset,'A',v) for v in nodes):candidates.append({'edges':[list(e) for e in subset],'weight':sum(e[2] for e in subset)})
 assert min(x['weight'] for x in candidates)==6
 full_path=min(paths(nodes,edges,'A','D'));tree_path=paths(nodes,tree,'A','D')[0];assert full_path[0]==3 and tree_path[0]==6
 disconnected,c,unused=forest(nodes+['U'],edges);assert c==2 and len(disconnected)==3
 negative,cneg,unused=forest(['X','Y'],[('X','Y',-1)]);assert cneg==1 and negative==[('X','Y',-1)]
 zero,czero,unused=forest(['X','Y'],[('X','Y',0)]);assert czero==1 and zero==[('X','Y',0)]
 reordered,_,_=forest(nodes,list(reversed(edges)));assert reordered==tree
 return {'runtime':platform.python_version(),'nodes':nodes,'edges':[list(e) for e in edges],'kruskal_trace':trace,'chosen_tree':[list(e) for e in tree],'tree_weight':6,'all_ten_three_edge_subsets_checked':10,'connected_spanning_candidates':candidates,'shortest_path_full_graph':{'cost':full_path[0],'nodes':full_path[1]},'path_inside_mst':{'cost':tree_path[0],'nodes':tree_path[1]},'with_isolated_U':{'components':c,'edges':[list(e) for e in disconnected]},'negative_edge_fixture':[list(e) for e in negative],'zero_edge_fixture':[list(e) for e in zero],'scope':'Fixed small integer undirected fixtures and deterministic tie policy; a forest when disconnected, not shortest-path tree or operational network-cost optimization. No Java execution.'}
if __name__=='__main__':print(json.dumps(demo(),ensure_ascii=True,indent=2))