n个点m条边，n<=1e6,初始的时候是连通的。第i个点权值是ai，现删掉一些边使得剩余连通分量的总权值最大。定义连通分量的权值，如果连通分量的包含奇数个点，则为-\sum ai,如果包含偶数个点，则为\sum ai. 首先初始n是偶数个点，则不用删边。 若n是奇数个点，则可以分成若干奇数个点+若干偶数个点。 我们发现奇数个点的连通块大小必然不超过1，原因在于假设3个点的连通块，分成2+1会更优。 因此n是奇数个点，目标是分成若干个孤立点+若干偶数个点。 再想想看，这些孤立点是什么。 第一种情况：可以变成一个非割点+(n-1)个点的偶图 第二种情况: 若非割点都很大怎么办，那么就要把割点作为孤立点。 割点作孤立点也只删除一个吗？反证：假如有>=3个割点作孤立点，那么能找到比它更优的(删1个)，考虑4个正方形，割点连接相邻两个正方形。但是不是哪个割点都可以可以，得满足删除后连通块大小都为偶数。 这两种情况取个最小值。 寻找割点可以用tarjan算法来求解

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
const int N=1e6+2,M=2e6+2;

int n,m;
int a[N];
int h[N],e[M],ne[M],idx;
int dfn[N],low[N],timestamp;
int siz[N];
LL sum,ans; 

void add(int a,int b)
{
	e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

void tarjan(int u)
{
	siz[u]=1;
	bool flag=true;
	dfn[u]=low[u]=++timestamp;
	
	for(int i=h[u];~i;i=ne[i])
	{
		int j=e[i];
		if(!dfn[j])
		{
			tarjan(j);
			siz[u]+=siz[j];
			low[u]=min(low[u],low[j]);
			if(low[j]>=dfn[u]&&(siz[j]&1))flag=false;  
		}
		else low[u]=min(low[u],dfn[j]);
	}
	
	if(flag)ans=min(ans,(LL)a[u]);
}

int main()
{
	int T;
	scanf("%d", &T);
	while (T -- )
	{		
		timestamp=sum=idx=0;
		
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&a[i]);
			h[i]=-1;
			dfn[i]=0;
			sum+=a[i];
		}
		for(int i=1;i<=m;i++)
		{
			int u,v;
			scanf("%d%d",&u,&v);
			add(u,v),add(v,u);
		}
		
		if(n%2==0) printf("%lld\n",sum);
		else
		{
			ans=sum; 
			tarjan(1);
			printf("%lld\n",sum-2*ans);	
		}
	}
	return 0;
}