#include <iostream>
#include <string>
#include <cstdio>
#include <queue>

using namespace std;

const int MAXN = 110;

struct nume {
    string a, b;
    int coada;

    nume (int _coada = -1) {
        coada = _coada;
    }
}v[MAXN];

int n, m;
deque<int> cozi[MAXN];

int main() {
    //freopen("b.in", "r", stdin);

    cin >> n >> m;

    for (int i = 1; i <= m; ++i) {
        string a, b; cin >> a >> b;
        v[i].a = a;
        v[i].b = b;
        v[i].coada = -1;
    }

    int que = 0;
    cin >> que;

    for (int q = 1; q <= que; ++q) {
        int type; cin >> type;
        if (type == 1) {
            int c; cin >> c;
            while(!cozi[c].empty()) {
                int x = cozi[c].front();
                cozi[c].pop_front();
                v[x].coada = -1;
            }
        }
        else if (type == 2) {
            string a; int c;
            cin >> c >> a;
            int j;
            for (j = 1; j <= m; ++j)
                if (v[j].a == a || v[j].b == a)
                    break;
            v[j].coada = c;
            cozi[c].push_back(j);
        }
        else if (type == 3) {
            int x; cin >> x;
            int t = cozi[x].front();
            cozi[x].pop_front();
            v[x].coada = -1;
        }
        else if (type == 4) {
            int x; cin >> x;
            for (int i = cozi[x].size() - 1; i >= 0; --i) {
                cout << v[cozi[x][i]].a << " " << v[cozi[x][i]].b;
                if (i != 0)
                    cout << " ";
            }
            if (cozi[x].size() == 0)
                cout << -1;
            cout << "\n";
        }
        else if (type == 5) {
            string a; cin >> a;
            int okay = 0;
            for (int i = 1; i <= m; ++i) {
                if (v[i].a == a || v[i].b == a) {
                    cout << v[i].coada << "\n";
                    okay = 1;
                }
            }
            if (!okay)
                cout << -1 << "\n";
        }
    }

    return 0;
}