题解：CF2109D D/D/D

#include<bits/stdc++.h>
#define int long long
#define PII pair<int,int>
#define INF 1e12
#define cc cin
#define oo cout
#define nm tie(0)
using namespace std;
const int N=2e5+5;
int t,n,m,k,sum;
int dis[N][2],b[N][2],a[N],c[N];
vector<int> ve[N];
signed main(){
//	freopen("1.out","r",stdin);
	//freopen(".out","w",stdout);
	ios::sync_with_stdio(false);
	cc.nm;
	oo.nm;
	cin>>t;
	while(t--){
		cin>>n>>m>>k;
		for(int i=1;i<=n;i++) b[i][0]=b[i][1]=0,dis[i][0]=dis[i][1]=INF,ve[i].clear();
		int omax=0,jmax=0,ok=0,jk=0;
		a[1]=a[2]=c[1]=c[2]=0;
		sum=0;
		for(int i=1,x;i<=k;i++){
			cin>>x;
			sum+=x;
			if(x%2==1) a[++jk]=x;
			else c[++ok]=x;
		}
		for(int i=1,x,y;i<=m;i++){
			cin>>x>>y;
			ve[x].push_back(y);
			ve[y].push_back(x);
		}
		sort(a+1,a+jk+1,greater<int>{});
		sort(c+1,c+ok+1,greater<int>{});
		if(sum%2==0) omax=sum;
		else omax=sum-a[jk],jmax=sum;
		if(sum%2==0&&jk) jmax=sum-a[jk];
//		cout<<omax<<" "<<jmax<<"\n";
		dis[1][0]=0;
		queue<PII> q;
		q.push({1,0});
		while(!q.empty()){
			auto [u,v]=q.front();
			q.pop();
			if(b[u][v]) continue;
			b[u][v]=1;
			for(int x:ve[u]){
				if(dis[x][v^1]>dis[u][v]+1){
					dis[x][v^1]=dis[u][v]+1;
					q.push({x,v^1});
				}
			}
		}
		cout<<1;
		for(int i=2;i<=n;i++){
			if(dis[i][0]!=INF&&dis[i][0]<=omax){
				cout<<1;
			}
			else if(dis[i][1]!=INF&&dis[i][1]<=jmax){
				cout<<1;
			}
			else cout<<0;
		}
		cout<<"\n";
	} 
	return 0;
}
/*
2
2 1 1
1
1 2
2 1 1
2
1 2
*/