#include #include #include using namespace std; using namespace atcoder; using mint = modint998244353; #define rep(i,n) for (int i = 0; i < (n); ++i) #define Inf32 1000000001 #define Inf64 4000000000000000001LL mint dfs(int cv,int pv,vector> &E,vector &res,vector &b, vector &v,vector &u){ mint ret = 0; rep(i,E[cv].size()){ int ii = E[cv][i]; int to = cv ^ u[ii] ^ v[ii];; if(to==pv)continue; mint r = dfs(to,cv,E,res,b,u,v); res[ii] = b[to] - r; ret += res[ii]; } return ret; } vector get(int n,vector u,vector v,vector b){ vector> E(n); rep(i,n-1){ E[u[i]].push_back(i); E[v[i]].push_back(i); } vector res(n-1); dfs(0,-1,E,res,b,u,v); return res; } unsigned long xor128() { static unsigned long x=123456789, y=362436069, z=521288629, w=88675123; unsigned long t=(x^(x<<11)); x=y; y=z; z=w; return (w=(w^(w>>19))^(t^(t>>8))); } int main(){ int n,m; cin>>n>>m; vector b(n); rep(i,n){ int bb; cin>>bb; b[i] = bb; } vector u(m),v(m); vector idx; dsu D(n); dsu D2(n*2); int ii = -1; rep(i,m){ cin>>u[i]>>v[i]; u[i]--,v[i]--; } rep(_,30){ vector is(m); rep(i,m){ is[i] = i; swap(is[i],is[xor128()%(i+1)]); } dsu D(n),D2(n*2); idx.clear(); rep(i,m){ int ci = is[i]; if(!D.same(u[ci],v[ci])){ D.merge(u[ci],v[ci]); D2.merge(u[ci],v[ci]+n); D2.merge(u[ci]+n,v[ci]); idx.push_back(ci); } else{ D2.merge(u[ci],v[ci]+n); D2.merge(u[ci]+n,v[ci]); if(D2.same(u[ci],u[ci]+n) || D2.same(v[ci],v[ci]+n)){ if(ii==-1)ii = ci; } } } if(ii!=-1)break; } vector u2,v2; rep(i,idx.size()){ u2.push_back(u[idx[i]]); v2.push_back(v[idx[i]]); } vector res = get(n,u2,v2,b); { vector cur(n); vector ans(m); rep(i,res.size()){ ans[idx[i]] = res[i]; cur[u[idx[i]]] += res[i]; cur[v[idx[i]]] += res[i]; } if(cur == b){ rep(i,m){ if(i!=0)cout<<' '; cout<