#include <bits/stdc++.h>

#define DMAX 120
using namespace std;
deque <int> d[DMAX];
map <string, string> name;
map <string, int> m;
string s, s1, s2;
bool ticket[DMAX];
int n, m2, a, x, k, t, nr;
vector <string> sn;
int ghiseu[DMAX];

int main()
{

    cin>>n>>m2;

    for(int i=1;i<=m2;i++)
        {
            cin>>s1>>s2;
            m[s1]=k;
            m[s2]=k;
            string ss=s1+" "+s2;
            sn.push_back(ss);
            k++;
        }
        cin>>t;
    for(int i=1;i<=t;i++)
    {

        cin>>nr;

        if(nr==1)
        {
            cin>>x;
            ticket[x]=1-ticket[x];
            if(ticket[x]==false)
            {
                for(int i=0;i<d[x].size();++i)
                    ghiseu[d[x][i]]=-1;
                d[x].clear();
            }
        }
        if(nr==2)
        {
            cin>>x;
            cin>>s;
            ghiseu[m[s]]=x;
            d[x].push_back(m[s]);
        }
        if(nr==3)
        {
            cin>>x;
            ghiseu[d[x][0]]=-1;
            d[x].pop_front();
        }
        if(nr==4)
        {
            cin>>x;
            if(d[x].empty())
                cout<<"-1\n";
            else for(int i=d[x].size()-1;i>=0;i--)
                cout<<sn[d[x][i]]<<" \n"[i==0];
        }
        if(nr==5)
        {
            cin>>s;
            cout<<ghiseu[m[s]]<<'\n';
        }
    }
    return 0;

}