1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<string> 5 #define MAXN 1000010 6 #define LL long long 7 const LL INF = 0x7fffffffffffff; 8 using namespace std; 9 typedef struct{ 10 int to,next; 11 }Node; 12 Node edge[2*MAXN]; 13 int vis[MAXN/10],head[MAXN/10],val[MAXN/10]; 14 LL sum[MAXN/10],all_sum,ans; 15 LL My_abs(LL tmp){return tmp < 0 ? -tmp : tmp;} 16 void addedge(int u,int v,int k){ 17 edge[k].to = v; 18 edge[k].next = head[u]; 19 head[u] = k; 20 } 21 LL dfs_sum(int s){ 22 vis[s] = 1; 23 sum[s] = val[s]; 24 for(int i = head[s];~i;i = edge[i].next){ 25 int u = edge[i].to; 26 if(!vis[u]) sum[s] += dfs_sum(u); 27 } 28 return sum[s]; 29 } 30 void dfs_minabs(int s){ 31 vis[s]= 1; 32 for(int i = head[s];~i;i = edge[i].next){ 33 int u = edge[i].to; 34 if(!vis[u]){ 35 dfs_minabs(u); 36 ans = min(ans,My_abs(all_sum - 2*sum[u])); 37 } 38 } 39 } 40 int main(){ 41 int n,m,cas = 0; 42 freopen("in.c","r",stdin); 43 while(~scanf("%d%d",&n,&m) && (m+n) ){ 44 int k = 1,tmp,u,v; 45 all_sum = 0; 46 for(int i = 1;i <= n;i ++) scanf("%d",&tmp),val[i] = tmp,all_sum += tmp; 47 memset(head,-1,sizeof(head)); 48 for(int i = 0;i < m;i ++){ 49 scanf("%d%d",&u,&v); 50 addedge(u,v,k++); 51 addedge(v,u,k++); 52 } 53 memset(vis,0,sizeof(vis)); 54 dfs_sum(1); 55 ans = INF; 56 memset(vis,0,sizeof(vis)); 57 dfs_minabs(1); 58 if(n == 1) ans = val[1]; 59 printf("Case %d: %lld ",++cas,ans); 60 } 61 return 0; 62 }