"""Original precedence-only DAG earliest-finish exercise, unlimited resources."""
from itertools import combinations
import json

def schedule(durations,edges,reverse_roots=False):
 if type(durations) is not dict or not 1<=len(durations)<=6 or any(type(k) is not str or not k or type(v) is not int or not 0<=v<=10 for k,v in durations.items()) or type(edges) is not list or any(type(x) is not tuple or len(x)!=2 or any(y not in durations for y in x) or x[0]==x[1] for x in edges) or len(set(edges))!=len(edges):raise ValueError('1..6 unique jobs/nonnegative integer durations, distinct valid edges')
 before={x:[] for x in durations};after={x:[] for x in durations}
 for u,v in edges:before[v].append(u);after[u].append(v)
 degree={x:len(before[x]) for x in durations};available=sorted(x for x in durations if not degree[x]);order=[];rows=[];ef={};paths={}
 while available:
  available.sort(reverse=reverse_roots);u=available.pop(0);order.append(u)
  if before[u]:
   es=max(ef[x] for x in before[u]);pred=min(x for x in before[u] if ef[x]==es);path=paths[pred]+[u]
  else:es=0;pred=None;path=[u]
  ef[u]=es+durations[u];paths[u]=path;rows.append({'job':u,'duration':durations[u],'predecessors':sorted(before[u]),'ES':es,'EF':ef[u],'chosen_max_predecessor':pred,'path':path})
  for v in after[u]:
   degree[v]-=1
   if degree[v]==0:available.append(v)
 if len(order)!=len(durations):raise ValueError('cycle')
 end=min(durations,key=lambda x:(-ef[x],x))
 return {'topological_order':order,'jobs':rows,'finish_by_job':ef,'project_finish':ef[end],'critical_path':paths[end]}

def all_paths_oracle(durations,edges):
 out=[];followers={x:[v for u,v in edges if u==x] for x in durations}
 def explore(path):
  out.append({'path':path,'end':path[-1],'duration':sum(durations[x] for x in path)})
  for v in followers[path[-1]]:
   assert v not in path;explore(path+[v])
 for node in durations:explore([node])
 return out

def checked(d,e):
 a=schedule(d,e);b=schedule(d,e,True);paths=all_paths_oracle(d,e);oracle={u:max(x['duration'] for x in paths if x['end']==u) for u in d};assert a['finish_by_job']==b['finish_by_job']==oracle and a['project_finish']==max(x['duration'] for x in paths)
 assert sum(d[x] for x in a['critical_path'])==a['project_finish']
 return {'input_durations':d,'input_edges':e,'schedule':a,'alternative_topological_order':b['topological_order'],'all_paths_oracle':paths}

def demo():
 d={'A':3,'B':2,'C':4,'D':1,'E':2};e=[('A','C'),('B','C'),('C','D'),('B','E')];main=checked(d,e);assert main['schedule']['project_finish']==8 and main['schedule']['critical_path']==['A','C','D']
 extra=[checked({'A':2,'B':2,'C':1},[('A','C'),('B','C')]),checked({'A':1,'B':3,'C':10},[('A','B')]),checked({'A':0},[])]
 possible=list(combinations('ABCD',2));checks=0
 for mask in range(64):
  edges=[r for i,r in enumerate(possible) if mask&(1<<i)];checked(dict(A=1,B=2,C=1,D=2),edges);checks+=1
 rejected=[]
 for label,dd,ee in [('cycle',dict(A=1,B=1),[('A','B'),('B','A')]),('negative',dict(A=-1),[]),('bool',dict(A=True),[]),('unknown',dict(A=1),[('A','X')]),('repeated_edge',dict(A=1,B=2),[('A','B'),('A','B')]),('empty',{},[])]:
  try:schedule(dd,ee)
  except ValueError:rejected.append(label)
  else:raise AssertionError('expected rejection')
 return {'authored_main':main,'serial_single_resource_total':sum(d.values()),'serial_total_is_not_unlimited_resource_finish':sum(d.values())!=8,'ties_isolated_zero_duration_cases':extra,'all64_forward_edge_DAG_oracles':checks,'invalid_cases_rejected':rejected,'scope':'precedence-only unlimited resources, arbitrary authored time unit, no execution/queuing/latency/real schedule or capacity benchmark; critical path maximizes duration, not number of nodes'}
if __name__=='__main__':print(json.dumps(demo(),ensure_ascii=True,indent=2))