R=range
def T(g,s):
 q=[[s]]
 while q:A=q.pop(0);yield(l:={b for i in A for a,b in g if a==i});q+=l,
def f(g,e,s):
 q,a,D,v=[(e,0,s,0)],[(e,s)],{},[]
 while q:
  E,c,S,B=q.pop(0);v+=B,;J=1
  if c<len(E):
   if-1==E[c]:q+=(E,c+1,s,B),;continue
   for i in next(T(g,E[c])):
    O=[*E];J=0
    if i-S:O[c]=i;q+=[(O,c+1,S,B)]*-~-((O,S)in a)
    else:O[c]=-1;q+=(O,c+1,S,B+1),
   q+=[(O,c+1,S,B)]*J
  else:
   t,L=T(g,S),0
   for i in R(max(sum(k==-1for k in E)+1,1)):
    for I in R(L,L:=i+1):M=next(t)
    for I in M:
     O=[*E];x=B
     for y in R(len(E)):G=O[y]==I;O[y]=[O[y],-1][G];x+=G;v+=x,
     if(O,I)not in a:q+=(O,0,I,x),;a+=(O,I),
 return max(v)
 
print(f([(0, 1), (1, 2)], [0, 2], 1))
print(f([(0, 1), (1, 2), (2, 3), (3, 0)], [0, 1], 2))
print(f([(0, 1), (1, 2), (2, 3), (3, 0)], [1], 0))
print(f([(0, 1), (1, 2), (2, 3), (3, 0), (1, 4), (4, 5), (5, 6), (6, 7), (7, 8), (8, 9), (9, 10), (10, 11), (11, 3)], [2, 6], 0))

Uj1yYW5nZQpkZWYgVChnLHMpOgogcT1bW3NdXQogd2hpbGUgcTpBPXEucG9wKDApO3lpZWxkKGw6PXtiIGZvciBpIGluIEEgZm9yIGEsYiBpbiBnIGlmIGE9PWl9KTtxKz1sLApkZWYgZihnLGUscyk6CiBxLGEsRCx2PVsoZSwwLHMsMCldLFsoZSxzKV0se30sW10KIHdoaWxlIHE6CiAgRSxjLFMsQj1xLnBvcCgwKTt2Kz1CLDtKPTEKICBpZiBjPGxlbihFKToKICAgaWYtMT09RVtjXTpxKz0oRSxjKzEscyxCKSw7Y29udGludWUKICAgZm9yIGkgaW4gbmV4dChUKGcsRVtjXSkpOgogICAgTz1bKkVdO0o9MAogICAgaWYgaS1TOk9bY109aTtxKz1bKE8sYysxLFMsQildKi1+LSgoTyxTKWluIGEpCiAgICBlbHNlOk9bY109LTE7cSs9KE8sYysxLFMsQisxKSwKICAgcSs9WyhPLGMrMSxTLEIpXSpKCiAgZWxzZToKICAgdCxMPVQoZyxTKSwwCiAgIGZvciBpIGluIFIobWF4KHN1bShrPT0tMWZvciBrIGluIEUpKzEsMSkpOgogICAgZm9yIEkgaW4gUihMLEw6PWkrMSk6TT1uZXh0KHQpCiAgICBmb3IgSSBpbiBNOgogICAgIE89WypFXTt4PUIKICAgICBmb3IgeSBpbiBSKGxlbihFKSk6Rz1PW3ldPT1JO09beV09W09beV0sLTFdW0ddO3grPUc7dis9eCwKICAgICBpZihPLEkpbm90IGluIGE6cSs9KE8sMCxJLHgpLDthKz0oTyxJKSwKIHJldHVybiBtYXgodikKIApwcmludChmKFsoMCwgMSksICgxLCAyKV0sIFswLCAyXSwgMSkpCnByaW50KGYoWygwLCAxKSwgKDEsIDIpLCAoMiwgMyksICgzLCAwKV0sIFswLCAxXSwgMikpCnByaW50KGYoWygwLCAxKSwgKDEsIDIpLCAoMiwgMyksICgzLCAwKV0sIFsxXSwgMCkpCnByaW50KGYoWygwLCAxKSwgKDEsIDIpLCAoMiwgMyksICgzLCAwKSwgKDEsIDQpLCAoNCwgNSksICg1LCA2KSwgKDYsIDcpLCAoNywgOCksICg4LCA5KSwgKDksIDEwKSwgKDEwLCAxMSksICgxMSwgMyldLCBbMiwgNl0sIDApKQ==