#include <iostream>
#include <cstring>
using namespace std;
int n,m,i,q[101][101],t,qu,j,poz[101],nr;
char car[101][3][21],s[21],ch;
int main()
{
    cin>>n>>m;
    for(i=1;i<=m;i++) {cin>>car[i][1]>>car[i][2]; cin.get();}
    cin>>t;
    for(i=1;i<=t;i++)
    {
        cin>>nr; if(nr!=5)
            cin>>qu;
        if(nr==1) {q[qu][0]=0; for(j=1;j<=m;j++) if(poz[j]==qu) poz[j]=0;}
        if(nr==2)
        {
            cin>>s;
            for(j=1;j<=m;j++)
                    if (strcmp(car[j][1],s)==0||strcmp(car[j][2],s)==0) {q[qu][++q[qu][0]]=j;
                    poz[j]=qu;
            }
        }
        if(nr==3)
        {
            poz[q[qu][1]]=0;
            for(j=1;j<q[qu][0];j++) q[qu][j]=q[qu][j+1];
            q[qu][0]--;
        }
        if(nr==4)
        {
            if(q[qu][0]==0) cout<<-1;
            else for(j=q[qu][0];j>=1;j--) cout<<car[q[qu][j]][1]<<' '<<car[q[qu][j]][2]<<' ';
            cout<<'\n';
        }
        if(nr==5)
        {
            cin>>s;
            for(j=1;j<=m;j++)
                if((strcmp(s,car[j][1])==0)||(strcmp(s,car[j][2])==0))
                    if(poz[j]) cout<<poz[j]<<'\n';
                    else cout<<-1<<'\n';
        }
    }
    return 0;
}