有起点终点的限制的路径覆盖
首先tarjan缩点成DAG
似乎不能按照二分匹配的做法做
那么建立源汇拆点i,i'，这两点之间连一条下界为1上界无穷的边，
其它边都是下界为0，上界正无穷
然后就是有源有汇的最小流，之前在bzoj2502介绍过
const inf=;
type node=record
po,flow,next:longint;
end; var w,e:array[..] of node;
be,p,q,c,dfn,low,cur,a,b:array[..] of longint;
v,f:array[..] of boolean;
na,nb,h,ss,tt,t,te,s,len,n,m,i,x,y,j:longint; function min(a,b:longint):longint;
begin
if a>b then exit(b) else exit(a);
end; procedure add(x,y:longint);
begin
inc(len);
w[len].po:=y;
w[len].next:=q[x];
q[x]:=len;
end; procedure build(x,y,f:longint);
begin
inc(len);
e[len].po:=y;
e[len].flow:=f;
e[len].next:=p[x];
p[x]:=len;
end; procedure tarjan(x:longint);
var i,y:longint;
begin
inc(h);
dfn[x]:=h;
low[x]:=h;
v[x]:=true;
inc(t);
c[t]:=x;
f[x]:=true;
i:=q[x];
while i<> do
begin
y:=w[i].po;
if not v[y] then
begin
tarjan(y);
low[x]:=min(low[x],low[y]);
end
else if f[y] then low[x]:=min(low[x],low[y]);
i:=w[i].next;
end;
if low[x]=dfn[x] then
begin
inc(s);
while c[t+]<>x do
begin
y:=c[t];
be[y]:=s;
f[y]:=false;
dec(t);
end;
end;
end; procedure sap(s,t:longint);
var q,u,i,j,tmp:longint;
begin
fillchar(c,sizeof(c),);
fillchar(dfn,sizeof(dfn),);
for i:= to t do
cur[i]:=p[i];
u:=s;
dfn[]:=t+;
while c[s]<t+ do
begin
i:=cur[u];
while i<>- do
begin
j:=e[i].po;
if (e[i].flow>) and (c[u]=c[j]+) then
begin
cur[u]:=i;
low[j]:=u;
u:=j;
if u=t then
begin
while u<>s do
begin
u:=low[u];
j:=cur[u];
dec(e[j].flow);
inc(e[j xor ].flow);
end;
end;
break;
end;
i:=e[i].next;
end;
if i=- then
begin
dec(dfn[c[u]]);
if dfn[c[u]]= then exit;
q:=-;
tmp:=t;
i:=p[u];
while i<>- do
begin
j:=e[i].po;
if e[i].flow> then
if c[j]<tmp then
begin
q:=i;
tmp:=c[j];
end;
i:=e[i].next;
end;
cur[u]:=q;
c[u]:=tmp+;
inc(dfn[c[u]]);
if u<>s then u:=low[u];
end;
end;
end; function check:boolean;
var i:longint;
begin
i:=p[ss];
while i<>- do
begin
if (e[i].flow>) and (e[i].po<>t) then exit(false);
i:=e[i].next;
end;
exit(true);
end; begin
readln(te);
while te> do
begin
dec(te);
len:=;
fillchar(p,sizeof(p),);
fillchar(q,sizeof(q),);
readln(n,m,na,nb);
for i:= to na do
read(a[i]);
for i:= to nb do
read(b[i]);
for i:= to m do
begin
readln(x,y);
add(x,y);
end;
fillchar(v,sizeof(v),false);
fillchar(f,sizeof(f),false);
fillchar(c,sizeof(c),);
s:=;
for i:= to n do
if not v[i] then
begin
h:=;
t:=;
tarjan(i);
end;
len:=-;
t:=*s+;
ss:=*s+;
tt:=*s+;
for i:= to na do
begin
build(,be[a[i]],inf);
build(be[a[i]],,);
end;
for i:= to nb do
begin
build(be[b[i]]+s,t,inf);
build(t,be[b[i]]+s,);
end;
for i:= to n do
begin
j:=q[i];
while j<> do
begin
y:=be[w[j].po];
if y<>be[i] then
begin
build(be[i]+s,y,inf);
build(y,be[i]+s,);
end;
j:=w[j].next;
end;
end;
for i:= to s do
begin
build(i,i+s,inf);
build(i+s,i,);
build(ss,i+s,);
build(i+s,ss,);
build(i,tt,);
build(tt,i,);
end;
sap(ss,tt);
build(t,,inf);
build(,t,);
sap(ss,tt);
if check then writeln(e[len].flow)
else writeln('no solution');
end;
end.