import json,random,sys
def nb(a,v):
    r=[];m=a[v]
    while m:
        b=m&-m;r.append(b.bit_length()-1);m^=b
    return r
def c4(n,a):
    s=0
    for u in range(n):
        for w in range(u+1,n):
            k=bin(a[u]&a[w]).count('1')
            if k>1:s+=k*(k-1)//2
    return s//2
def cyc(n,a,L,cap=0):
    if L>n:return(False,True)
    N=[nb(a,v) for v in range(n)];B=[cap if cap else -1]
    def f(s,c,vis,d):
        if B[0]==0:raise RuntimeError()
        if B[0]>0:B[0]-=1
        if d==L:return bool((a[c]>>s)&1)
        for w in N[c]:
            if w>s and not ((vis>>w)&1):
                if f(s,w,vis|1<<w,d+1):return True
        return False
    try:
        for s in range(n):
            if f(s,s,1<<s,1):return(True,True)
    except RuntimeError:return(False,False)
    return(False,True)
def nc(n,a,L):
    if L>n:return 0
    N=[nb(a,v) for v in range(n)];t=[0]
    def f(s,c,vis,d):
        if d==L:
            if (a[c]>>s)&1:t[0]+=1
            return
        for w in N[c]:
            if w>s and not ((vis>>w)&1):f(s,w,vis|1<<w,d+1)
    for s in range(n):f(s,s,1<<s,1)
    return t[0]
def gen(n,degs,rng):
    hi=set(v for v,d in enumerate(degs) if d>3)
    for _ in range(400):
        st=[]
        for v,d in enumerate(degs):st+=[v]*d
        rng.shuffle(st);a=[0]*n;ok=True
        for i in range(0,len(st),2):
            x,y=st[i],st[i+1]
            if x==y or ((a[x]>>y)&1) or (x in hi and y in hi):ok=False;break
            a[x]|=1<<y;a[y]|=1<<x
        if ok:return a
    return None
def mv(n,a,rng):
    for _ in range(40):
        x=rng.randrange(n)
        if not a[x]:continue
        nx=nb(a,x);y=nx[rng.randrange(len(nx))]
        u=rng.randrange(n)
        if not a[u]:continue
        nu=nb(a,u);v=nu[rng.randrange(len(nu))]
        if x==u or y==v or x==v or y==u:continue
        if ((a[x]>>u)&1) or ((a[y]>>v)&1):continue
        return(x,y,u,v)
    return None
def sw(a,m):
    x,y,u,v=m
    a[x]^=1<<y;a[y]^=1<<x;a[u]^=1<<v;a[v]^=1<<u
    a[x]^=1<<u;a[u]^=1<<x;a[y]^=1<<v;a[v]^=1<<y
def fams(n):
    o=[]
    if (3*n)%2==0:o.append([3]*n)
    if n%2:o.append([4]+[3]*(n-1));o.append([4,4,4]+[3]*(n-3))
    else:o.append([4,4]+[3]*(n-2))
    return o
def ck(n,a):
    for v in range(n):
        if (a[v]>>v)&1 or bin(a[v]).count('1')<3:return False
    if c4(n,a):return False
    if cyc(n,a,8)[0]:return False
    h,c=cyc(n,a,16)
    if h or not c:return False
    if n>=32:
        h,c=cyc(n,a,32)
        if h or not c:return False
    return True
def one(n,rng,rs,ia,ib):
    st={'n':n,'attempts':0,'c4free':0,'c8free':0,'c16probed':0,'minc16':None,'c16free':0}
    for degs in fams(n):
        for _ in range(rs):
            a=gen(n,degs,rng)
            if a is None:continue
            st['attempts']+=1
            cur=c4(n,a);T=1.2
            for _ in range(ia):
                m=mv(n,a,rng)
                if m is None:break
                sw(a,m);nv=c4(n,a)
                if nv<=cur or rng.random()<pow(2.718281828,-(nv-cur)/T):cur=nv
                else:sw(a,m)
                T=max(0.02,T*0.99985)
                if cur==0:break
            if c4(n,a):continue
            st['c4free']+=1
            c8=nc(n,a,8);T=1.5
            for _ in range(ib):
                m=mv(n,a,rng)
                if m is None:break
                sw(a,m)
                if c4(n,a):sw(a,m);T=max(0.02,T*0.9999);continue
                n8=nc(n,a,8)
                if n8<=c8 or rng.random()<pow(2.718281828,-(n8-c8)/T):c8=n8
                else:sw(a,m)
                T=max(0.02,T*0.9998)
                if c8==0:break
            if nc(n,a,8):continue
            st['c8free']+=1;st['c16probed']+=1
            if n<=31:
                k=nc(n,a,16)
                if st['minc16'] is None or k<st['minc16']:st['minc16']=k
                if k:continue
            else:
                h,cp=cyc(n,a,16,8000000)
                if h or not cp:continue
                h,cp=cyc(n,a,32,3000000)
                if h or not cp:continue
            if ck(n,a):
                e=[]
                for x in range(n):
                    for y in nb(a,x):
                        if y>x:e.append([y,x])
                st['c16free']+=1
                return e,st
    return None,st
def main():
    p=[x for x in sys.argv[1:] if not x.startswith('--')]
    if len(p)<2:
        print(json.dumps({'ok':False,'error':'usage: jsp82_submit.py FROM TO'}));return
    A,B=int(p[0]),int(p[1])
    if B<A:A,B=B,A
    o={'ok':True,'range':[A,B],'counterexamples':[],'codes':{'used_pow2_only':False,'deterministic':True},'per_n':[]}
    for n in range(A,B+1):
        k=max(1,(n-6)//2);ia=ib=(580*k) if n<=31 else (260*k)
        rng=random.Random(0x51500082+n)
        e,st=one(n,rng,4,ia,ib)
        o['per_n'].append(st)
        if e is not None:o['counterexamples'].append({'type':'witness','n':n,'edges':e})
    print(json.dumps(o))
main()