#include<iostream>
#include<cstdio>
#include<set>
#include<vector>
#define N 1000
#define inf 1e9
using namespace std;
int read()
{
    char c=0;
    int sum=0;
    while (c<'0'||c>'9') c=getchar();
    while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
    return sum;
}
struct reads
{
    int num,data;
};
struct node
{
    int num;
    unsigned __int128 d1,d2,d3,d4;
    bool operator < (const node &t)const
    {
	return num<t.num;
    }
};
int n,m,k,res,cnt[N+1],W[N+1],bt[N+1],tong[N+1],length,fa[N+1],deg[N+1],depth[N+1],SX[N+1],SY[N+1],X[N+1],Y[N+1],vst[N+1];
node ans,delta[N+1],dp[N+1][2][2][2][2],F[2][2][2],G[2][2][2];
bool used[N+1],vis[N+1],ed[N+1],cl[N+1];
vector<reads>E[N+1];
set<int>s[N+1];
node operator + (node a,node b)
{
    return (node){a.num+b.num,a.d1|b.d1,a.d2|b.d2,a.d3|b.d3,a.d4|b.d4};
}
void Adder(node &x,node d)
{
    x=(x<d)?d:x;
    return;
}
void add(int x,int y,int z)
{
    E[x].push_back((reads){y,z}),E[y].push_back((reads){x,z});
    return;
}
void dfs(int x)
{
    used[x]=1;
    for (int i=0;i<E[x].size();++i)
	if (!used[E[x][i].num])
	    cnt[x]++,fa[E[x][i].num]=x,depth[E[x][i].num]=depth[x]+1,dfs(E[x][i].num),vis[E[x][i].data]=1;
    return;
}
void dfs2(int x)
{
    for (int i=0;i<E[x].size();++i)
	if (fa[E[x][i].num]==x)
	    ed[E[x][i].num]=s[x].find(bt[E[x][i].num])!=s[x].end(),dfs2(E[x][i].num);
    return;
}
void dfs3(int x)
{
    bool opt=0;
    for (int i=0;i<E[x].size();++i)
	if (fa[E[x][i].num]==x)
	    dfs3(E[x][i].num),opt=1;
    if (!opt)
    {
	if (vst[x]!=1) dp[x][0][0][0][0]=(node){0,0,0,0};
	if (vst[x]!=2) dp[x][1][1][1][1]=delta[x];
	return;
    }
    for (int op=0;op<=1;++op)
    {
	if (!op&&vst[x]==1) continue;
	if (op&&vst[x]==2) continue;
	opt=0;
	for (int op2=0;op2<=1;++op2)
	    for (int op3=0;op3<=1;++op3)
		for (int op4=0;op4<=1;++op4)
		    F[op2][op3][op4]=(node){(int)(-inf),0,0,0};
	if (!op) F[0][0][0]=(node){0,0,0,0};
	else F[1][0][0]=delta[x];
	for (int i=0;i<E[x].size();++i)
	    if (fa[E[x][i].num]==x)
	    {
		for (int op2=0;op2<=1;++op2)
		    for (int op3=0;op3<=1;++op3)
			for (int op4=0;op4<=1;++op4)
			    G[op2][op3][op4]=(node){(int)(-inf),0,0,0};
		if (!opt)
		{
		    for (int op2=0;op2<=1;++op2)
			for (int op3=0;op3<=1;++op3)
			    for (int op4=0;op4<=1;++op4)
				for (int op5=0;op5<=1;++op5)
				{
				    if (op&&op2) continue;
				    if (ed[E[x][i].num]&&op&&op3) continue;
				    for (int op6=0;op6<=1;++op6)
					for (int op7=0;op7<=1;++op7)
					    for (int op8=0;op8<=1;++op8)
						Adder(G[(bt[x]==bt[E[x][i].num])?op3:op6][op4][op5],F[op6][op7][op8]+dp[E[x][i].num][op2][op3][op4][op5]);
				}
		    opt=1;
		}
		else
		{
		    for (int op2=0;op2<=1;++op2)
			for (int op3=0;op3<=1;++op3)
			    for (int op4=0;op4<=1;++op4)
				for (int op5=0;op5<=1;++op5)
				{
				    if (op&&op2) continue;
				    if (ed[E[x][i].num]&&op&&op3) continue;
				    for (int op6=0;op6<=1;++op6)
					for (int op7=0;op7<=1;++op7)
					    for (int op8=0;op8<=1;++op8)
					    {
						if (op8&&op4) continue;
						Adder(G[(bt[x]==bt[E[x][i].num])?op3:op6][op7][op5],F[op6][op7][op8]+dp[E[x][i].num][op2][op3][op4][op5]);
					    }
				}
		}
		for (int op2=0;op2<=1;++op2)
		    for (int op3=0;op3<=1;++op3)
			for (int op4=0;op4<=1;++op4)
			    F[op2][op3][op4]=G[op2][op3][op4];
	    }
	for (int op2=0;op2<=1;++op2)
	    for (int op3=0;op3<=1;++op3)
		for (int op4=0;op4<=1;++op4)
		    Adder(dp[x][op][op2][op3][op4],F[op2][op3][op4]);
    }
    return;
}
int main()
{
    int x;
    bool opt;
    n=read(),m=read(),ans=(node){(int)(-inf),0,0,0};
    for (int i=1;i<=n;++i) W[i]=read();
    for (int i=1;i<=n;++i)
    {
	delta[i].num=W[i];
	if (i<=128) delta[i].d1|=((unsigned __int128)(1)<<(i-1));
	else if (i<=256) delta[i].d2|=((unsigned __int128)(1)<<(i-129));
	else if (i<=384) delta[i].d3|=((unsigned __int128)(1)<<(i-257));
	else delta[i].d4|=((unsigned __int128)(1)<<(i-383));
    }
    for (int i=1;i<=m;++i) SX[i]=read()+1,SY[i]=read()+1,add(SX[i],SY[i],i),deg[SX[i]]++,deg[SY[i]]++;
    depth[1]=1,dfs(1);
    for (int i=1;i<=m;++i)
	if (!vis[i])
	{
	    if (depth[SX[i]]>depth[SY[i]]) swap(SX[i],SY[i]);
	    x=SY[i];
	    while (x!=SX[i]) bt[x]=SY[i],x=fa[x];
	    s[SX[i]].insert(SY[i]);
	}
    dfs2(1);
    k=read();
    for (int i=1;i<=k;++i) X[i]=read()+1,Y[i]=read()+1,deg[X[i]]++,deg[Y[i]]++;
    for (int i=1;i<=n;++i)
	if (deg[i]>=12||(deg[i]==1&&k==1))
	    tong[++length]=i;
    for (int i=0;i<(1<<length);++i)
    {
	for (int j=1;j<=n;++j) vst[j]=0;
	for (int j=1;j<=length;++j)
	{
	    if (i&(1<<(j-1))) vst[tong[j]]=1;
	    else vst[tong[j]]=2;
	}
	opt=1;
	for (int j=1;j<=k;++j)
	    if (vst[X[j]]==1&&vst[Y[j]]==1)
		opt=0;
	for (int j=1;j<=m;++j)
	    if (vst[SX[j]]==1&&vst[SY[j]]==1)
		opt=0;
	if (!opt) continue;
	for (int j=1;j<=n;++j)
	    for (int op=0;op<=1;++op)
		for (int op2=0;op2<=1;++op2)
		    for (int op3=0;op3<=1;++op3)
			for (int op4=0;op4<=1;++op4)
			    dp[j][op][op2][op3][op4]=(node){(int)(-inf),0,0,0};
	for (int j=1;j<=k;++j)
	{
	    if (vst[X[j]]==1) vst[Y[j]]=2;
	    if (vst[Y[j]]==1) vst[X[j]]=2;
	}
	dfs3(1);
	if (cnt[1]==1)
	{
	    for (int op=0;op<=1;++op)
		for (int op2=0;op2<=1;++op2)
		    for (int op3=0;op3<=1;++op3)
			for (int op4=0;op4<=1;++op4)
			{
			    if (op&&op3) continue;
			    if (op&&op4) continue;
			    Adder(ans,dp[1][op][op2][op3][op4]);
			}
	}
	else
	{
	    for (int op=0;op<=1;++op)
		for (int op2=0;op2<=1;++op2)
		    for (int op3=0;op3<=1;++op3)
			for (int op4=0;op4<=1;++op4)
			{
			    if (op3&&op4) continue;
			    Adder(ans,dp[1][op][op2][op3][op4]);
			}
	}
    }
    for (int i=1;i<=n;++i)
    {
	if (i<=128)
	{
	    if (ans.d1&((unsigned __int128)(1)<<(i-1))) cl[i]=1,res++;
	}
	else if (i<=256)
	{
	    if (ans.d2&((unsigned __int128)(1)<<(i-129))) cl[i]=1,res++;
	}
	else if (i<=384)
	{
	    if (ans.d3&((unsigned __int128)(1)<<(i-257))) cl[i]=1,res++;
	}
	else
	{
	    if (ans.d4&((unsigned __int128)(1)<<(i-383))) cl[i]=1,res++;
	}
    }
    printf("%d %d\n",ans.num,res);
    for (int i=1;i<=n;++i)
	if (cl[i])
	    printf("%d ",i-1);
    puts("");
    return 0;
}