#include <fstream>
#include <iostream>
#include <vector>
#include <bitset>
#include <string.h>
#include <algorithm>
#include <iomanip>
#include <math.h>
#include <time.h>
#include <stdlib.h>
#include <set>
#include <map>
#include <string>
#include <queue>
#include <deque>

using namespace std;

const char infile[] = "input.in";
const char outfile[] = "output.out";

ifstream fin(infile);
ofstream fout(outfile);

const int MAXN = 1005;
const int oo = 0x3f3f3f3f;

typedef vector<int> Graph[MAXN];
typedef vector<int> :: iterator It;

const inline int min(const int &a, const int &b) { if( a > b ) return b;   return a; }
const inline int max(const int &a, const int &b) { if( a < b ) return b;   return a; }
const inline void Get_min(int &a, const int b)    { if( a > b ) a = b; }
const inline void Get_max(int &a, const int b)    { if( a < b ) a = b; }

queue <int> Q[MAXN];
map<string, int> mp;
map<int, pair<string, string> > mpi;
int N, M, T, where[MAXN];
bitset <MAXN> Used;
vector <int> v;

void write(queue <int> &q) {
    if(q.empty())
        return;
    int x = q.front();
    q.pop();
    write(q);
    v.push_back(x);
}

int main() {
    #ifndef ONLINE_JUDGE
    freopen(infile, "r", stdin);
    freopen(outfile, "w", stdout);
    #endif // ONLINE_JUDGE
    cin >> N >> M;
    for(int i = 1 ; i <= M ; ++ i) {
        string a, b;
        cin >> a >> b;
        mp[a] = i;
        mp[b] = i;
        mpi[i] = make_pair(a, b);
    }
    cin >> T;
    for(int q = 1 ; q <= T ; ++ q) {
        int op, x;
        string a;
        cin >> op;
        if(op == 1) {
            cin >> x;
            Used[x] = (! Used[x]);
            if(Used[x] == 0)
                while(!Q[x].empty()) {
                    where[Q[x].front()] = 0;
                    Q[x].pop();
                }
        }
        if(op == 2) {
            cin >> x >> a;
            if(where[mp[a]])
                continue;
            if(Used[x] == 0)
                continue;
            Q[x].push(mp[a]);
            where[mp[a]] = x;
        }
        if(op == 3) {
            cin >> x;
            if(Q[x].empty())
                continue;
            where[Q[x].front()] = 0;
            Q[x].pop();
        }
        if(op == 4) {
            v.clear();
            cin >> x;
            queue <int> actQ = Q[x];
            if(Q[x].empty())
                cout << "-1\n";
            else write(Q[x]);
            Q[x] = actQ;
            for(int i = 0 ; i + 1 < v.size() ; ++ i) {
                cout << mpi[v[i]].first << ' ' << mpi[v[i]].second << ' ';
            }
            if(v.size())
                cout << mpi[v[v.size() - 1]].first << ' ' << mpi[v[v.size() - 1]].second << '\n';
        }
        if(op == 5) {
            cin >> a;
            if(where[mp[a]] != 0)
                cout << where[mp[a]] << '\n';
            else cout << "-1\n";
        }
    }
    return 0;
}