1 #include <iostream>  2 #include <cstdio>  3 #include <cstring>  4 #include <algorithm>  5 #include <vector>  6   7 #define KT ch[ch[root][1]][0]  8 #define LC ch[x][0]  9 #define RC ch[x][1] 10 #define N 61001 11 #define M 61000 12 #define Q 500000 13 using namespace std; 14  15  16 int fa[N]; 17 int ch[N][2]; 18 int sz[N]; 19 int top1; 20 int top2; 21 int ss[N]; 22 int que[N]; 23 int nodque[N],top3; 24 int val[N]; 25 int nodbelong[N]; 26 int ini[N]; 27 const int inf=1e9; 28 vector<int> g[N]; 29 struct SplayTree{ 30     int root; 31     void rotate(int x,bool f){ 32         int y=fa[x]; 33         int z=fa[y]; 34         pushdown(y); 35         pushdown(x); 36         ch[y][!f]=ch[x][f]; 37         fa[ch[x][f]]=y; 38         fa[x]=z; 39         if (z) { 40             ch[z][ch[z][1]==y] = x; 41         } 42         ch[x][f] = y; 43         fa[y]=x; 44         pushup(y); 45     } 46     void splay(int x, int g) { 47         int y = fa[x]; 48         pushdown(x); 49         while(y!=g){ 50             int z= fa[y]; 51             bool f = (ch[y][0]==x); 52             if(z != g && f == (ch[z][0]==y)){ 53                 rotate(y,f); 54             } 55             rotate(x,f); 56             y=fa[x]; 57         } 58         pushup(x); 59         if(g==0) root = x; 60     } 61     void rotateTo(int k,int g) { 62         int x=root; 63         pushdown(x); 64         while(sz[LC] != k){ 65             if(k<sz[LC]){ 66                 x=LC; 67             }else{ 68                 k -= sz[LC] + 1; 69                 x = RC; 70             } 71             pushdown(x); 72         } 73         splay(x,g); 74     } 75     void build(int l,int r,int f){ 76         if(l>r){ 77             return ; 78         } 79         int x = (l + r) >> 1; 80         LC = (x - 1 >= l)? (x - 1 + l)>> 1 :0; 81         RC = (r >= x + 1)? (x + 1 + r)>> 1 :0; 82         fa[x] = f; 83         build(l,x - 1,x); 84         build(x + 1,r,x); 85         pushup(x); 86     } 87     void erase(int x){ 88         if(x==0) 89             return; 90         int father= fa[x]; 91         int head = 0, tail=0; 92         for(que[tail++] =x ; head < tail; head++){ 93             ss[top2++] = que[head]; 94             if(ch[que[head]][0]){ 95                 que[tail++]=ch[que[head]][0]; 96             } 97             if(ch[que[head]][1]){ 98                 que[tail++] = ch[que[head]][1]; 99             }100         }101         ch[father][ch[father][1]==x]=0;102         pushup(father);103     }104     void makeTree(int &x, int l, int r, int f ,vector<int>& g){105         if(l > r){106             return;107         }108         int m=(l+r)>>1;109         newNode(x, ini[g[m]],g[m]);110         makeTree(LC,l,m-1,x,g);111         makeTree(RC,m+1,r,x,g);112         fa[x]=f;113         pushup(x);114     }115     void treaval(int x){116         if (x) {117             pushdown(x);118             treaval(LC);119             printf("@%d",val[x]);120 121             //ans[cnt++]=val[x];122             treaval(RC);123         }124     }125     void dfs(int x){126         if (x) {127             pushdown(x);128             dfs(LC);129             nodque[top3++]=x;130             dfs(RC);131         }132     }133     void newNode(int &x,int c,int id){134         if(id){135             x=id;//直接另节点号一致136         }137         else if(top2){138             x = ss[--top2];139         } else {140             x = ++top1;//top1从n+1，开始141         }142         LC = 0;143         RC = 0;144         fa[x] =0;145         sz[x] = 1;146 147         val[x]=c;148     }149     void pushdown(int x){150 151     }152     void pushup(int x){153         sz[x]=1+sz[LC]+sz[RC];154     }155 156     void debug(){157         treaval(root);158         cout<<endl;159     }160     void cutTo(int l,int r,int c){161         rotateTo(l-1,0);162         rotateTo(r+1,root);163         int tmp=KT;164         KT=0;165         pushup(ch[root][1]);166         pushup(root);167 168         rotateTo(c,0);169         rotateTo(c+1,root);170         fa[tmp]=ch[root][1];171         KT=tmp;172         pushup(ch[root][1]);173         pushup(root);174     }175 176     void init(vector<int>&g){177 178         root=0;179         int n=g.size();180         newNode(root,inf,0);181         newNode(ch[root][1],-inf,0);182         fa[ch[root][1]]=root;183         //for(int i=1;i<=n;i++)scanf("%d",&num[i]);184         makeTree(KT,0,n-1,ch[root][1],g);185         pushup(ch[root][1]);186         pushup(root);187     }188     int size(){189         return sz[root]-2;190     }191     int find(int x,int v,int cur){192         if(val[x]>=v){193             cur=x;194             return RC?find(RC,v,cur):cur;195         }else{196             return LC?find(LC,v,cur):cur;197         }198 //        if(val[LC]<v){199 //            return find(LC,v);200 //        }else if(val[RC]>v){201 //            return find(RC,v);202 //        }else203 //            return val[x]<v?LC:RC;204     }205     void insert(int y){//将y节点插入splay206         int x=find(root,val[y],root);207         splay(x,0);208         int s=sz[LC]+1;209         rotateTo(s,root);210         fa[y]=ch[root][1];211         ch[y][0]=0;212         ch[y][1]=0;213         KT=y;214         sz[y]=1;215         pushup(ch[root][1]);216         pushup(root);217     }218     void merge(SplayTree spt){219         top3=0;220         spt.dfs(spt.root);221         rotateTo(1,0);222         int tmp=nodbelong[root];223         for(int i=1;i<top3-1;i++){224             insert(nodque[i]);225             nodbelong[nodque[i]]=tmp;226         }227     }228     void change(int x,int k){229         splay(x,0);230         int s=sz[LC];231         rotateTo(s-1,0);232         rotateTo(s+1,root);233 234         KT=0;235         pushup(ch[root][1]);236         pushup(root);237 238         val[x]=k;239         insert(x);240     }241     int query(int k){242         if(k>size()||k<=0)return 0;243         rotateTo(k,0);244         return val[root];245     }246 247 }spt[N];248 249 struct edge{250     int flag;251     int to;252     int next;253 }e[M<<1];254 int head[N],num;255 void _add(int u,int v){256     e[num].flag=0;257     e[num].to=v;258     e[num].next=head[u];259     head[u]=num++;260 }261 void add(int u,int v){262     _add(u,v);263     _add(v,u);264 }265 struct Ques{266     char op;267     int x,k;268     void set(char o,int xx,int kk){269         op=o;270         x=xx;271         k=kk;272     }273 }questa[Q];274 int top4;275 int vis[N];276 277 void dfs(int x,int id){278     vis[x]=1;279     nodbelong[x]=id;280     for(int i=head[x];i!=-1;i=e[i].next)if(!e[i].flag&&!vis[e[i].to]){281         dfs(e[i].to,id);282     }283 }284 int cmp(int i,int j){285     return ini[i]>ini[j];286 }287 void init(int n,int m){288     memset(head,-1,sizeof(int)*(n+1));289     num=top4=0;290     top1=n;top2=0;291     memset(vis,0,sizeof(int)*(n+1));292 }293 void solve( int n,int m){294 295     int u,v;296     int x,k;297     char op[10];298 299     init(n,m);300     for(int i=1;i<=n;i++){301         scanf("%d",&ini[i]);302     }303     for(int i=0;i<m;i++){304         scanf("%d%d",&u,&v);305         add(u,v);306     }307     top4=0;308     while(scanf("%s",op),op[0]!=‘E‘){309         if(op[0]==‘D‘){310             scanf("%d",&x);311             int id=(x-1)*2;312             questa[top4++].set(op[0],e[id].to,e[id^1].to);313             e[id].flag=1;314             e[id^1].flag=1;315         }else if(op[0]==‘Q‘){316             scanf("%d%d",&x,&k);317             questa[top4++].set(op[0],x,k);318         }else{319             scanf("%d%d",&x,&k);320             questa[top4++].set(op[0],x,ini[x]);321             ini[x]=k;322         }323     }324     int cnt=0;325     for(int i=1;i<=n;i++)if(!vis[i]){326         dfs(i,cnt++);327     }328     for(int i=1;i<=n;i++){329         g[nodbelong[i]].push_back(i);330     }331     for(int i=0;i<cnt;i++){332         sort(g[i].begin(),g[i].end(),cmp);333 //        for(int j=g[i].size()-1;j>=0;j--){334 //            cout<<g[i][j]<<" ";335 //        }336 //        cout<<endl;337     }338     for(int i=0;i<cnt;i++){339         spt[i].init(g[i]);340     }341 //    for(int i=0;i<cnt;i++)342 //        cout<<spt[i].size()<<endl;343     double ans=0;344     int ret=0;345     while(top4--){346         char op=questa[top4].op;347         x=questa[top4].x;k=questa[top4].k;348         if(op==‘D‘){349             int id1=nodbelong[x];350             int id2=nodbelong[k];351             int sz1=spt[id1].size();352             int sz2=spt[id2].size();353             if(id1==id2)continue;354             if(sz1>sz2){355                 spt[id1].merge(spt[id2]);356             }else{357                 spt[id2].merge(spt[id1]);358             }359         }else if(op==‘C‘){360             int id=nodbelong[x];361 362             spt[id].change(x,k);363         }else{364             int id=nodbelong[x];365             //spt[id].debug();366             //int t=spt[id].query(k);367             ans+=spt[id].query(k);368             //cout<<t<<endl;369             ret++;370         }371     }372     printf("%.6lf\n",(double)ans/ret);373     for(int i=0;i<cnt;i++)g[i].clear();374 }375 int main()376 {377     int n,m;378 379     int cas=1;380     while(scanf("%d%d",&n,&m),n||m){381         printf("Case %d: ",cas++);382         solve(n,m);383     }384     return 0;385 }