#include<cstdio>
#include<deque>
#include<cstring>
using namespace std;
int n,m,i,q,op,x,c[105],poz[105],y;
char a[105][105],b[105][105],s[105];
deque<int> v[105];
int main()
{
	//freopen("test.in","r",stdin);
	//freopen("test.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        scanf("%s",a[i]);
        scanf("%s",b[i]);
    }
    scanf("%d",&q);
    for(;q;q--)
    {
        scanf("%d",&op);
        if(op==1)
        {
            scanf("%d",&x);
            c[x]=1-c[x];
            if(c[x]==0)
            {
                for(deque<int>::iterator it=v[x].begin();it!=v[x].end();it++)
                    poz[*it]=0;
                v[x].clear();
            }
        }
        else if(op==2)
        {
            scanf("%d",&x);
            scanf("%s",s);
            for(i=1;i<=m;i++)
                if(strcmp(s,a[i])==0 || strcmp(s,b[i])==0)
                {
                    poz[i]=x;
                    v[x].push_back(i);
                    break;
                }
        }
        else if(op==3)
        {
            scanf("%d",&x);
            y=v[x].front();
            poz[y]=0;
            v[x].pop_front();
        }
        else if(op==4)
        {
            scanf("%d",&x);
            if(v[x].empty()) printf("-1\n");
            else
            {
                for(i=v[x].size()-1;i>=1;i--) printf("%s %s ",a[v[x][i]],b[v[x][i]]);
                printf("%s %s\n",a[v[x][0]],b[v[x][0]]);
            }
        }
        else
        {
            scanf("%s",s);
            for(i=1;i<=m;i++)
                if(strcmp(s,a[i])==0 || strcmp(s,b[i])==0)
                {
                    if(poz[i]) printf("%d\n",poz[i]);
                    else printf("-1\n");
                    break;
                }
        }
    }
	return 0;
}