C++ :

#include <cstdio>
#include <iostream>
#include <algorithm>

using namespace std;

struct Edge{
    int u,v;
};

struct Question{
    int u,v;
    bool ex;
};


Edge input[1000001];Question question[1000001];
int father[1000001],k1,k2,n,m,q,cs=0;
char in,ans[1000001];

int find(int i)
{
    if(father[i]!=i) father[i]=find(father[i]);
    return father[i];
}

bool comp(Edge a,Edge b)
{
    if(a.u==b.u) return a.v<b.v;
    return a.u<b.u;
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        father[i]=i;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&input[i].u,&input[i].v);
        if(input[i].u>input[i].v)
        {
            input[i].u^=input[i].v;
            input[i].v^=input[i].u;
            input[i].u^=input[i].v;
        }
    }
    scanf("%d",&q);
    for(int i=1;i<=q;i++)
    {
        cin>>in;
        scanf("%d%d",&k1,&k2);
        if(in=='D')
        {
            m++;
            if(k1>k2)
            {
                k1^=k2;
                k2^=k1;
                k1^=k2;
            }
            input[m].u=k1;
            input[m].v=k2;
            question[i].ex=1;
        }
        else
        {
            question[i].ex=0;
        }
        question[i].u=k1;
        question[i].v=k2;
    }
    sort(input+1,input+m+1,comp);
    for(int i=1;i<=m;i++)
    {
        if((input[i].u==input[i+1].u&&input[i].v==input[i+1].v)||(i!=1&&input[i].u==input[i-1].u&&input[i].v==input[i-1].v)) {continue;}
        k1=find(input[i].u);
        k2=find(input[i].v);
        if(k1!=k2) father[k1]=k2;
    }
    for(int i=q;i>=1;i--)
    {
        k1=find(question[i].u);
        k2=find(question[i].v);
        if(question[i].ex==0)
        {
            cs++;
            if(k1==k2)
                ans[cs]='C';
            else
                ans[cs]='D';
        }
        else if(k1!=k2)
        {
            father[k1]=k2;
        }
    }
    for(int i=cs;i>=1;i--)
        printf("%c\n",ans[i]);
    return 0;
}