"""Original all-component BFS bipartition and parent-LCA odd-cycle witness."""
from collections import deque
from itertools import combinations,product
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 known unique-ID graph<=8nodes, no loops/parallel edges')

def two_color(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)
 colors={};parent={};depth={};trace=[]
 for root in sorted(nodes):
  if root in colors:continue
  colors[root]=0;parent[root]=None;depth[root]=0;q=deque([root])
  while q:
   u=q.popleft()
   for v in sorted(adj[u]):
    if v not in colors:colors[v]=1-colors[u];parent[v]=u;depth[v]=depth[u]+1;q.append(v);trace.append({'action':'color','node':v,'parent':u,'color':colors[v],'depth':depth[v]})
    elif colors[v]==colors[u]:
     first=[];cur=u
     while cur is not None:first.append(cur);cur=parent[cur]
     second=[];cur=v
     while cur not in first:second.append(cur);cur=parent[cur]
     lca=cur;cycle=first[:first.index(lca)+1]+list(reversed(second))+[u]
     return {'bipartite':False,'colors_partial':colors,'parent':parent,'depth':depth,'conflict_edge':[u,v],'odd_closed_cycle':cycle,'trace':trace}
 return {'bipartite':True,'colors':colors,'parent':parent,'depth':depth,'partition':[[x for x in sorted(nodes) if colors[x]==c] for c in [0,1]],'odd_closed_cycle':None,'trace':trace}

def oracle(nodes,edges):
 for assignment in product([0,1],repeat=len(nodes)):
  color=dict(zip(nodes,assignment))
  if all(color[u]!=color[v] for u,v in edges):return True
 return False

def checked(nodes,edges):
 out=two_color(nodes,edges);assert out['bipartite']==oracle(nodes,edges)
 if out['bipartite']:assert set(out['colors'])==set(nodes) and all(out['colors'][u]!=out['colors'][v] for u,v in edges)
 else:
  cyc=out['odd_closed_cycle'];ee={frozenset(e) for e in edges};assert cyc[0]==cyc[-1] and (len(cyc)-1)%2==1 and len(set(cyc[:-1]))==len(cyc)-1 and all(frozenset((u,v)) in ee for u,v in zip(cyc,cyc[1:]))
 return {'nodes':nodes,'edges':edges,'result':out}

def demo():
 square=checked(list('ABCDU'),[('A','B'),('B','C'),('C','D'),('D','A')]);pentagon=checked(list('ABCDEU'),[('A','B'),('B','C'),('C','D'),('D','E'),('E','A')]);assert square['result']['bipartite'] and len(pentagon['result']['odd_closed_cycle'])==6
 poss=list(combinations('ABCDE',2));checks=0;bip=0
 for mask in range(1024):
  x=checked(list('ABCDE'),[e for i,e in enumerate(poss) if mask&(1<<i)]);bip+=x['result']['bipartite'];checks+=1
 empty=checked([],[]);isolates=checked(list('ABC'),[])
 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:two_color(nn,ee,d)
  except ValueError:rejected.append(label)
  else:raise AssertionError('expected rejection')
 return {'square_with_isolate_positive':square,'pentagon_with_isolate_negative':pentagon,'all1024_five_vertex_graph_coloring_oracles':{'cases':checks,'bipartite':bip,'nonbipartite':checks-bip,'oracle':'all2^5assignments independently tested per graph'},'empty_and_isolate_cases':[empty,isolates],'invalid_graphs_rejected':rejected,'scope':'original BFS plus LCA reconstruction, not copied source DFS/Java run; closed odd-cycle certificate fully validated including nonancestor conflict endpoints; unweighted undirected simple graph only, not matching/stable marriage/SAT general solver or real object identity'}
if __name__=='__main__':print(json.dumps(demo(),ensure_ascii=True,indent=2))