这个题当时打多校的时候有思路，但是代码能力差，没有写出来
事后看zimpha巨巨的题解，看了觉得基本差不多
核心思路：就是找出割点，然后变成森林，然后树形dp就可以搞了
关键就在重新构图上，缩完点以后，一个割点至少在两个点双里面，这个时候
把割点拿出来，分别和点双连边，也就是说，缩完的点双是不包含割点的，这个可以人为搞一下
（像有的点双里面只包含一个桥边，如果把割点拿出来，点双里面没有点了，这个时候把点双的权值积设为1就好）
然后说是树形dp，其实就是逆元搞一搞，这个很简单，树形dp只处理割点的答案
注意：这个图不联通，这是一个点，还有孤立点，我一直wa在孤立点上，（我的点双模板只能解决至少包含两个点的连通图，这个题丰满了我的模板，感谢）
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <vector>
#include <math.h>
#include <stack>
#include <map>
using namespace std;
typedef long long LL;
const int N = 1e5+;
const LL mod = 1e9+;
LL qpow(LL a,LL b){
LL ret=;
while(b){
if(b&)ret=(ret*a)%mod;
b>>=;
a=(a*a)%mod;
}
return ret;
}
int head[N<<],tot,T,n,m;
struct Edge{
int u,v,next;
}edge[N*];
void addedge(int u,int v){
edge[tot].u=u;
edge[tot].v=v;
edge[tot].next=head[u];
head[u]=tot++;
}
int low[N],dfn[N],clk,cnt,belbcc[N];
bool iscut[N];
vector<int>bcc[N],cut;
stack<int>s;
void init(){
memset(dfn,,sizeof(dfn));
memset(head,-,sizeof(head));
memset(belbcc,,sizeof(belbcc));
tot=clk=cnt=;
cut.clear();
}
LL w[N],bccw[N<<],ret[N],blkw[N<<],zong;
bool vis[N<<];
int blk,bel[N<<];
void dfs(int u,int f){
dfn[u]=low[u]=++clk;
int child=;
if(head[u]==-){
++cnt;bcc[cnt].clear();
bcc[cnt].push_back(u);
belbcc[u]=cnt;
return ;
}
for(int i=head[u];~i;i=edge[i].next){
int to=edge[i].v;
if(!dfn[to]){
++child;s.push(i);dfs(to,u);
low[u]=min(low[u],low[to]);
if(low[to]>=dfn[u]){
iscut[u]=true;++cnt;int x;bcc[cnt].clear();
do{
x=s.top();s.pop(); if(belbcc[edge[x].u]!=cnt){
bcc[cnt].push_back(edge[x].u);
belbcc[edge[x].u]=cnt;
} if(belbcc[edge[x].v]!=cnt){
bcc[cnt].push_back(edge[x].v);
belbcc[edge[x].v]=cnt;
}
}while(x!=i);
}
}
else if(dfn[to]<dfn[u]&&to!=f){
s.push(i);
low[u]=min(low[u],dfn[to]);
}
}
if(!f&&child==)iscut[u]=false;
if(iscut[u])cut.push_back(n+u),bccw[n+u]=w[u];
}
void predfs(int u,int f){
bel[u]=blk;blkw[blk]=blkw[blk]*bccw[u]%mod;
vis[u]=true;
for(int i=head[u];~i;i=edge[i].next){
int v=edge[i].v;
if(v==f)continue;
predfs(v,u);
}
}
LL treedp(int u,int f){
LL pro=,sum=,tmp;
vis[u]=false;
for(int i=head[u];~i;i=edge[i].next){
int v=edge[i].v;
if(v==f)continue;
tmp=treedp(v,u);
pro=pro*tmp%mod;
sum=(sum+tmp)%mod;
}
pro=pro*bccw[u]%mod;
if(u>n){
tmp=blkw[bel[u]];
tmp=tmp*qpow(pro,mod-)%mod;
sum=(sum+tmp)%mod;
tmp=zong-blkw[bel[u]];
while(tmp<)tmp+=mod;
ret[u-n]=(sum+tmp)%mod;
}
return pro;
}
int main(){
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&m);
for(int i=;i<=n;++i)scanf("%I64d",&w[i]);
init();
for(int i=;i<m;++i){
int u,v;scanf("%d%d",&u,&v);
addedge(u,v);addedge(v,u);
}
for(int i=;i<=n;++i)if(!dfn[i])dfs(i,);
tot=;memset(head,-,sizeof(head));
for(int i=;i<=cnt;++i){
bccw[i]=;
for(int j=;j<bcc[i].size();++j){
int u=bcc[i][j];
if(iscut[u]) addedge(i,u+n),addedge(u+n,i);
else bccw[i]=bccw[i]*w[u]%mod;
}
}
blk=;
for(int i=;i<=cnt;++i)
if(!vis[i]){++blk;blkw[blk]=;predfs(i,);}
for(int i=;i<cut.size();++i)
if(!vis[cut[i]]){++blk;blkw[blk]=;predfs(cut[i],);}
zong=;
for(int i=;i<=blk;++i)zong=(zong+blkw[i])%mod;
for(int i=;i<=cnt;++i)
if(vis[i])treedp(i,);
for(int i=;i<cut.size();++i)
if(vis[cut[i]])treedp(cut[i],);
LL ans=;
for(int i=;i<=n;++i){
if(iscut[i]){
ans=(ans+1ll*i*ret[i]%mod)%mod;
iscut[i]=false;
}
else{
int k=belbcc[i];
k=bel[k];
LL ad=;
if(w[i]!=blkw[k])ad=blkw[k]*qpow(w[i],mod-)%mod;
LL tmp=zong-blkw[k];
while(tmp<)tmp+=mod;
tmp=(tmp+ad)%mod;
ans=(ans+1ll*i*tmp%mod)%mod;
}
}
printf("%I64d\n",ans);
}
return ;
}