//考察点: 拆点 + 最大流
//思路: 把城市作为点拆开(把城市i拆成cap数组中的cap[i][i+n].其中i作为城市i的入,i+n作为城市i的出),原来的街道仍然作为边,但是边权是无穷大. 只要注意到BFS的时候 起点/终点是不需要拆的.(在cap[][]数组中就直接把起点/终点的入和出之间的边权赋值为0,使得BFS的时候不走起点/终点,实际上就相当于没有把起点/终点拆开.程序中的处理方法就是 cap[s][s+n] = 0;/cap[e][e+n] = 0;)
//提交情况; Wrong Answer 4次 Accepted 1次
WA 的原因是: BFS写错 做完一个CASE没有初始化cap数组导致错误
//收获: 对BFS有了更深的理解 对抽象出来的算法过程也有了具体的体会 吸取了不初始化的教训
//经验: 在学习一个代码的时候要手动模拟一下过程 好好理解算法的精髓 另外要加强联系 争取掌握用邻接表建图的方法
//ACcode
#include<stdio.h>
#include<memory.h>
#include<stdlib.h>
const int INF = 0x7fffffff;
int cap[201][201];
int s,t;
int que[201],pre[201];
int n,m;
bool vis[201];
bool findroad()
{
memset(vis,0,sizeof(vis));
int i,j;
int head = 0,tail = 0;
que[tail ++] = s;
while(head < tail)
{
j = que[head ++];
for(i = 1; i <= 2*n ;i ++)
{
if(!vis[i] && cap[j][i] > 0)
{
vis[i] = true;
pre[i] = j;
if(i == t) return true;
que[tail ++] = i;
}
}
}
return false;
}
int maxflow()
{
int flow = 0,i,min;
while(findroad())
{
min = INF;
for(i = t; i != s;i = pre[i])
{
if(cap[pre[i]][i] < min)
min = cap[pre[i]][i];
}
flow += min;
for(i = t; i != s;i = pre[i])
{
cap[pre[i]][i] -= min;
cap[i][pre[i]] += min;
}
}
return flow;
}
int main()
{
int T,x,y,i,j,tem,b,e;
scanf("%d", &T);
while(T--)
{
scanf("%d%d%d%d",&n,&m,&b,&e);
for(i = 1; i <= n;i ++)
{
scanf("%d",&tem);
cap[i][i+n] = tem;
}
s = b + n;
t = e;
cap[e][e+n]=0;
cap[s][s+n]=0;
for(i = 1; i <= m;i ++)
{
scanf("%d%d",&x,&y);
cap[x+n][y] = INF;
cap[y+n][x] = INF;
}
printf("%d\n",maxflow());
memset(cap,0,sizeof(cap));
}
return 0;
}