"""Simple undirected integer-labelled graphs: true-degree peeling, core
certificates, degeneracy triangle enumeration, density approximation/exact
integer-flow certificates. Standard library, stdout only, explicit checks."""
from fractions import Fraction as Q
from collections import deque,Counter
from itertools import combinations
import json

def check(ok,msg):
 if not ok:raise ValueError(msg)
def natural(x):return type(x) is int and x>=0

class Graph:
 def __init__(self,n,edges):
  check(natural(n),'vertex count');self.n=n;self.adj=[[] for _ in range(n)];self.edges=[]
  for e in edges:
   check(type(e) in (tuple,list) and len(e)==2,'edge record');u,v=e
   check(natural(u) and natural(v) and u<n and v<n and u!=v,'simple edge endpoints')
   self.adj[u].append(v);self.adj[v].append(u);self.edges.append((min(u,v),max(u,v)))
  stamp=[-1]*n
  for u in range(n):
   for v in self.adj[u]:
    check(stamp[v]!=u,'duplicate undirected edge');stamp[v]=u
  self.m=len(self.edges)
 def induced(self,vertices):
  keep=[False]*self.n
  for v in vertices:
   check(natural(v) and v<self.n and not keep[v],'distinct vertex subset');keep[v]=True
  return sum(keep[u] and keep[v] for u,v in self.edges)

def peel(g):
 n=g.n;degree=list(map(len,g.adj));head=[-1]*max(1,n);prev=[-1]*n;nxt=[-1]*n;alive=[True]*n
 def insert(v,d):
  w=head[d];nxt[v]=w;prev[v]=-1
  if w>=0:prev[w]=v
  head[d]=v
 def unlink(v,d):
  a,b=prev[v],nxt[v]
  if a>=0:nxt[a]=b
  else:head[d]=b
  if b>=0:prev[b]=a
 for v in reversed(range(n)):insert(v,degree[v])
 smallest=0;up=down=updates=0;order=[];core=[0]*n;delta=0;left=g.m;history=[]
 best_edges=0;best_count=1;best_index=0
 for t in range(n):
  while head[smallest]<0:smallest+=1;up+=1
  v=head[smallest];d=degree[v];unlink(v,d);alive[v]=False
  if left*best_count>best_edges*(n-t):best_edges=left;best_count=n-t;best_index=t
  history.append(dict(vertex=v,degree=d,vertices=n-t,edges=left))
  order.append(v);delta=max(delta,d);core[v]=delta;left-=d
  for u in g.adj[v]:
   if alive[u]:
    old=degree[u];unlink(u,old);degree[u]-=1;insert(u,degree[u]);updates+=1
    if degree[u]<smallest:down+=smallest-degree[u];smallest=degree[u]
 check(left==0 and updates==g.m,'edge retirement');check(down<=n and up<=2*n,'minimum pointer amortization')
 answer=order[best_index:] if n else []
 return dict(order=order,core=core,degeneracy=delta,history=history,approximation=answer,approximation_density=Q(best_edges,best_count) if n else None,work=dict(up=up,down=down,degree_updates=updates))

def verify_core(g,order,core):
 n=g.n;check(len(order)==len(core)==n,'core certificate length');pos=[-1]*n
 for t,v in enumerate(order):
  check(natural(v) and v<n and pos[v]<0,'vertex permutation');pos[v]=t
 for v in range(n):check(natural(core[v]),'natural core number')
 check(all(core[order[t]]<=core[order[t+1]] for t in range(n-1)),'nondecreasing core labels')
 for v in range(n):
  lower=sum(core[u]>=core[v] for u in g.adj[v]);upper=sum(pos[u]>pos[v] for u in g.adj[v])
  check(lower>=core[v] and upper<=core[v],'core lower support / deletion upper bound')
 return True

def triangles(g,order):
 n=g.n;check(len(order)==n,'order length');pos=[-1]*n
 for t,v in enumerate(order):
  check(natural(v) and v<n and pos[v]<0,'vertex permutation');pos[v]=t
 out=[[] for _ in range(n)]
 for u,v in g.edges:
  if pos[u]>pos[v]:u,v=v,u
  out[u].append(v)
 stamp=[-1]*n;answer=[];scans=0
 for u in order:
  for w in out[u]:stamp[w]=u
  for v in out[u]:
   for w in out[v]:
    scans+=1
    if stamp[w]==u:answer.append(tuple(sorted((u,v,w))))
 return dict(triangles=answer,two_step_scans=scans,max_outdegree=max(map(len,out),default=0))

def network(g,threshold):
 check(type(threshold) in (int,Q) and threshold>=0,'nonnegative rational threshold');lam=Q(threshold);p,q=lam.numerator,lam.denominator;s=g.n;t=s+1
 arcs=[]
 for v in range(g.n):arcs.extend([(s,v,q*len(g.adj[v])),(v,t,2*p)])
 for u,v in g.edges:arcs.extend([(u,v,q),(v,u,q)])
 return g.n+2,arcs,s,t,2*q*g.m

def maxflow(n,arcs,s,t):
 # BFS augmenting paths (Edmonds--Karp); original arcs and their reverses
 # retain distinct indices, including when original antiparallel arcs exist.
 residual=[];adj=[[] for _ in range(n)]
 for u,v,c in arcs:
  check(natural(c),'integer capacity');k=len(residual);residual.extend([[u,v,c],[v,u,0]]);adj[u].append(k);adj[v].append(k+1)
 total=0;augmentations=0
 while True:
  parent=[-1]*n;parent[s]=-2;queue=deque([s])
  while queue and parent[t]<0:
   u=queue.popleft()
   for k in adj[u]:
    _,v,c=residual[k]
    if c>0 and parent[v]==-1:parent[v]=k;queue.append(v)
  if parent[t]<0:break
  path=[];v=t
  while v!=s:k=parent[v];path.append(k);v=residual[k][0]
  amount=min(residual[k][2] for k in path)
  for k in path:residual[k][2]-=amount;residual[k^1][2]+=amount
  total+=amount;augmentations+=1
 flow=[c-residual[2*i][2] for i,(u,v,c) in enumerate(arcs)]
 return dict(value=total,flow=flow,cut=[v for v in range(n) if parent[v]!=-1],augmentations=augmentations)

def verify_flow(n,arcs,s,t,certificate):
 flow=certificate['flow'];cut=certificate['cut'];check(len(flow)==len(arcs),'flow length');inside=[False]*n;balance=[0]*n
 for v in cut:check(natural(v) and v<n and not inside[v],'cut set');inside[v]=True
 check(inside[s] and not inside[t],'source/sink cut');capacity=0
 for (u,v,c),f in zip(arcs,flow):
  check(natural(f) and f<=c,'capacity interval');balance[u]+=f;balance[v]-=f
  if inside[u] and not inside[v]:capacity+=c
 check(all(balance[v]==0 for v in range(n) if v not in (s,t)),'internal conservation')
 check(balance[s]==-balance[t]==certificate['value']==capacity,'matching flow and cut')
 return True

def threshold_query(g,lam):
 n,arcs,s,t,baseline=network(g,lam);cert=maxflow(n,arcs,s,t);verify_flow(n,arcs,s,t,cert)
 check(cert['value']<=baseline,'source cut baseline');side=[v for v in cert['cut'] if v<g.n]
 strict=cert['value']<baseline
 if strict:check(side and Q(g.induced(side),len(side))>lam,'strict improvement witness')
 return dict(strict=strict,side=side,baseline=baseline,certificate=cert)

def densest(g,record_history=True):
 if g.n==0:return dict(status='NO_NONEMPTY_SET',vertices=[],density=None,history=[],certificate=None)
 if g.m==0:return dict(status='OPTIMAL',vertices=[0],density=Q(0),history=[],certificate=threshold_query(g,Q(0))['certificate'])
 lo=Q(0);hi=Q(g.n-1,2);witness=list(range(g.n));history=[];calls=0
 while hi-lo>=Q(1,g.n*g.n):
  lam=(lo+hi)/2;r=threshold_query(g,lam);calls+=1
  if record_history:history.append(dict(threshold=lam,strict=r['strict'],side=r['side'],flow=r['certificate']['value'],baseline=r['baseline']))
  if r['strict']:lo=lam;witness=r['side']
  else:hi=lam
 rho=Q(g.induced(witness),len(witness));check(lo<rho<=hi,'rational bracket witness')
 final=threshold_query(g,rho);check(not final['strict'],'final optimum upper certificate')
 return dict(status='OPTIMAL',vertices=witness,density=rho,history=history,certificate=final['certificate'],bracket=(lo,hi),flow_calls=calls+1)

def verify_density(g,vertices,certificate):
 check(bool(vertices),'nonempty solution');rho=Q(g.induced(vertices),len(vertices));n,arcs,s,t,baseline=network(g,rho)
 verify_flow(n,arcs,s,t,certificate);check(certificate['value']==baseline,'all subset density upper bound');return True

def brute(g):
 # Exponential diagnostic only: does not participate in the algorithm bounds.
 cores=[0]*g.n;best=None;sets=[]
 for mask in range(1,1<<g.n):
  vs=[v for v in range(g.n) if mask>>v&1];rho=Q(sum((mask>>u&1) and (mask>>v&1) for u,v in g.edges),len(vs))
  if best is None or rho>best:best=rho;sets=[vs]
  elif rho==best:sets.append(vs)
  d=min(sum(mask>>u&1 for u in g.adj[v]) for v in vs)
  for v in vs:cores[v]=max(cores[v],d)
 tri=[c for c in combinations(range(g.n),3) if all(v in g.adj[u] for u,v in combinations(c,2))]
 return dict(core=cores,density=best,optimal_sets=sets,triangles=tri)

def encode(x):
 if isinstance(x,Q):return str(x)
 if isinstance(x,dict):return {k:encode(v) for k,v in x.items()}
 if isinstance(x,(tuple,list)):return [encode(v) for v in x]
 return x

def main():
 edges=list(combinations(range(4),2))+[(u,v) for u in (4,5) for v in range(6,14)]+[(0,14)];g=Graph(16,edges)
 p=peel(g);verify_core(g,p['order'],p['core']);tri=triangles(g,p['order']);exact=densest(g);verify_density(g,exact['vertices'],exact['certificate']);oracle=brute(g)
 check(p['core']==oracle['core'] and sorted(tri['triangles'])==oracle['triangles'] and exact['density']==oracle['density'],'main independent subset check')
 check(p['approximation_density']==Q(11,7) and exact['density']==Q(8,5),'main density values')
 boundaries=[]
 for n,es in [(0,[]),(1,[]),(4,[]),(2,[(0,1)]),(6,[(u,v) for u in range(3) for v in range(3,6)])]:
  h=Graph(n,es);a=peel(h);verify_core(h,a['order'],a['core']);b=triangles(h,a['order']);c=densest(h);ref=brute(h)
  check(a['core']==ref['core'] and sorted(b['triangles'])==ref['triangles'] and c['density']==ref['density'],'boundary')
  if n:verify_density(h,c['vertices'],c['certificate'])
  boundaries.append(dict(n=n,m=len(es),core=a['core'],triangles=b['triangles'],density=c['density'],status=c['status']))
 star=Graph(9,[(4,v) for v in range(9) if v!=4]);arbitrary=triangles(star,list(range(9)));proper=triangles(star,peel(star)['order'])
 check(arbitrary['two_step_scans']==16 and proper['two_step_scans']<=8,'star arbitrary orientation cost')
 failures=0
 for n,es in [(2,[(0,0)]),(2,[(0,1),(1,0)]),(2,[(0,2)]),(2,[(True,1)])]:
  try:Graph(n,es)
  except ValueError:failures+=1
 check(failures==4,'invalid graph rejections')
 bridge=Graph(16,edges+[(0,4)]);bp=peel(bridge);bt=triangles(bridge,bp['order']);bd=densest(bridge);verify_core(bridge,bp['order'],bp['core']);verify_density(bridge,bd['vertices'],bd['certificate'])
 check(bp['core']==p['core'] and sorted(bt['triangles'])==sorted(tri['triangles']) and bd['density']==Q(23,14),'bridge migration')
 print(json.dumps(encode(dict(status='PASS',main=dict(n=g.n,m=g.m,edges=g.edges,peeling=p,triangles=tri,exact=exact,thresholds={str(t):threshold_query(g,t) for t in [Q(3,2),Q(31,20),Q(8,5)]}),bridge=dict(n=bridge.n,m=bridge.m,peeling=bp,triangles=bt,exact=bd),boundaries=boundaries,star=dict(arbitrary=arbitrary,degeneracy=proper),invalid_inputs=failures)),ensure_ascii=False,indent=2,sort_keys=True))
if __name__=='__main__':main()