Python3, 691 bytes

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]
  if c<len(E):
   if E[c]==-1:q+=[(E,c+1,s,B)];continue
   J=1
   for i in next(T(g,E[c])):
    O=[*E];J=0
    if i!=S:
     O[c]=i
     if(O,S)not in a:J=0;q+=[(O,c+1,S,B)]
    else:O[c]=-1;q+=[(O,c+1,S,B+1)]
   if J:q+=[(O,c+1,S,B)]
  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,i+1):M=next(t)
    L=i+1
    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)

Try it online!

Python3, 691 bytes

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]
  if c<len(E):
   if E[c]==-1:q+=[(E,c+1,s,B)];continue
   J=1
   for i in next(T(g,E[c])):
    O=[*E];J=0
    if i!=S:
     O[c]=i
     if(O,S)not in a:J=0;q+=[(O,c+1,S,B)]
    else:O[c]=-1;q+=[(O,c+1,S,B+1)]
   if J:q+=[(O,c+1,S,B)]
  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,i+1):M=next(t)
    L=i+1
    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)

Try it online!

Also, a 808 byte solution that uses caching for faster execution: try it online