1 #include<bits/stdc++.h>
  2 #define F(i,a,b) for(int i=a;i<=b;++i)
  3 using namespace std;
  4 typedef pair<int,int>P;
  5 
  6 const int N=2e6+7;
  7 int _t,a[N];
  8 struct tree//键值可重，去重需要加num记录这个数的个数
  9 {
 10     int key,sz,f,ch[2];
 11     int add,rev;
 12 }T[N];
 13 
 14 struct Splay_tree
 15 {
 16     int root;
 17     void init(){root=0;}
 18     inline void nw(int &x,int key,int f)
 19     {
 20         T[++_t].key=key,T[_t].f=f,T[_t].sz=1;
 21         T[_t].ch[0]=T[_t].ch[1]=0,x=_t;
 22         T[_t].add=T[_t].rev=0;
 23     }
 24     inline void up(int x){T[x].sz=T[T[x].ch[0]].sz+T[T[x].ch[1]].sz+1;}
 25     void rotate(int x){
 26         int y=T[x].f,w=T[y].ch[1]==x;
 27         T[y].ch[w]=T[x].ch[w^1];
 28         if(T[x].ch[w^1])T[T[x].ch[w^1]].f=y;
 29         if(T[y].f){
 30             int z=T[y].f;
 31             if(T[z].ch[0]==y)T[z].ch[0]=x;
 32             if(T[z].ch[1]==y)T[z].ch[1]=x;
 33         }
 34         T[x].f=T[y].f,T[x].ch[w^1]=y,T[y].f=x;up(y);
 35     }
 36 
 37     void splay(int x,int w){
 38         int s=1,i=x,y;a[1]=x;
 39         while(T[x].f!=w){
 40             y=T[x].f;
 41             if(T[y].f!=w)(T[T[y].f].ch[0]==y)^(T[y].ch[0]==x)?rotate(x):rotate(y);
 42             rotate(x);
 43         }
 44         if(!w)root=x;
 45         up(x);
 46     }
 47     inline int find(int key) //返回值为key的节点 若无返回0 若有将其转移到根处
 48     {
 49         if(!root)return 0;
 50         int x=root;
 51         for(;x&&T[x].key!=key;)x=T[x].ch[T[x].key<key];
 52         if(x)splay(x,0);
 53         return x;
 54     }
 55     inline void ins(int key)//插入key键值
 56     {
 57         if(!root){nw(root,key,0);return;}
 58         int x=root,y=0;
 59         while(x)y=x,T[x].sz++,x=T[x].ch[T[x].key<key];
 60         nw(T[y].ch[T[y].key<key],key,y);
 61         splay(T[y].ch[T[y].key<key],0);
 62     }
 63     inline void det(int key)//删除值为key的节点1个
 64     {
 65         int x=find(key);
 66         if(!x)return;
 67         int y=T[x].ch[0],z=T[x].ch[1];
 68         while(T[y].ch[1])y=T[y].ch[1];
 69         while(T[z].ch[0])z=T[z].ch[0];
 70         if(!y&&!z)root=0;
 71         else if(!y)splay(z,0),T[z].ch[0]=0,up(z);
 72         else if(!z)splay(y,0),T[y].ch[1]=0,up(y);
 73         else splay(y,0),splay(z,y),T[z].ch[0]=0,up(z),up(y);
 74     }
 75     inline int kth(int k)//获得第k小的键值
 76     {
 77         if(k>T[root].sz||k<=0)return 0;
 78         k=T[root].sz-k+1;
 79         int x=root,tmp;
 80         while(1)
 81         {
 82             tmp=T[T[x].ch[0]].sz+1;
 83             if(k==tmp)break;
 84             if(k<tmp)x=T[x].ch[0];else k-=tmp,x=T[x].ch[1];
 85         }
 86         return T[x].key;
 87     }
 88 }spt[N];
 89 //--------------------------------
 90 int n,m,g[N],w[N],nxt[N],ed,x,vis[N],f[N],qed,cas;
 91 P edge[N];
 92 
 93 struct query
 94 {
 95     char cmd[2];
 96     int x,y;
 97 }q[N];
 98 
 99 void init(){_t=ed=0;F(i,1,n)spt[i].init(),f[i]=i,g[i]=0;}
100 void adg(int x,int c){w[++ed]=c,nxt[ed]=g[x],g[x]=ed;}
101 int find(int x){return x==f[x]?x:f[x]=find(f[x]);}
102 
103 void dfs(int r,int x)
104 {
105     if(!r)return;
106     spt[x].ins(T[r].key);
107     dfs(T[r].ch[0],x),dfs(T[r].ch[1],x);
108 }
109 
110 void merge(int x,int y)
111 {
112     int fx=find(x),fy=find(y);
113     if(fx==fy)return;
114     if(T[spt[fx].root].sz<T[spt[fy].root].sz)swap(fx,fy);
115     dfs(spt[fy].root,fx),f[fy]=fx;
116 }
117 
118 int main()
119 {
120     while(~scanf("%d%d",&n,&m),n+m)
121     {
122         init();
123         F(i,1,n)scanf("%d",&x),adg(i,x);
124         F(i,1,m)scanf("%d%d",&edge[i].first,&edge[i].second),vis[i]=0;
125         for(qed=0;;)
126         {
127             scanf("%s",q[++qed].cmd);
128             if(q[qed].cmd[0]==‘E‘)break;
129             else if(q[qed].cmd[0]==‘D‘)scanf("%d%d",&q[qed].x),vis[q[qed].x]=1;
130             else if(q[qed].cmd[0]==‘Q‘)scanf("%d%d",&q[qed].x,&q[qed].y);
131             else scanf("%d%d",&q[qed].x,&q[qed].y),adg(q[qed].x,q[qed].y);
132         }
133         F(i,1,n)spt[i].ins(w[g[i]]);
134         F(i,1,m)if(!vis[i])merge(edge[i].first,edge[i].second);
135         double ans=0;int cnt=0;
136         for(int i=qed-1;i>0;i--)
137         {
138             if(q[i].cmd[0]==‘Q‘)
139             {
140                 cnt++;
141                 int fx=find(q[i].x);
142                 ans+=spt[fx].kth(q[i].y);
143             }else if(q[i].cmd[0]==‘D‘)merge(edge[q[i].x].first,edge[q[i].x].second);
144             else
145             {
146                 int fx=find(q[i].x);
147                 spt[fx].det(w[g[q[i].x]]);
148                 g[q[i].x]=nxt[g[q[i].x]];
149                 spt[fx].ins(w[g[q[i].x]]);
150             }
151         }
152         printf("Case %d: %.6f\n",++cas,ans/cnt);
153     }
154     return 0;
155 }