#include <stdio.h>
#include <string.h>
#include <map>
#include <queue>
#include <string>
#include <vector>

using namespace std;

#define NMAX 1111

map<string, pair<string, string> > names;
map<string, int> qidx;
queue<pair<string, string> > q[NMAX];
vector<pair<string, string> > v;
char A[NMAX], B[NMAX], open[NMAX];
int N, M, T, i, op, x;

int main() {
	scanf("%d %d", &N, &M);
	for (i = 1; i <= M; i++) {
		scanf("%s %s", A, B);
		names[A] = make_pair(A, B);
		names[B] = make_pair(A, B);
		qidx[A] = qidx[B] = 0;
	}

	scanf("%d", &T);

	while (T--) {
		scanf("%d", &op);
		if (op == 1) {
			scanf("%d", &x);
			open[x] ^= 1;
			if (open[x] == 0) {
				while (q[x].size() > 0) {
					pair<string, string> p = q[x].front();
					q[x].pop();
					qidx[p.first] = qidx[p.second] = 0;
				}
			}
		} else if (op == 2) {
			scanf("%d %s", &x, A);
			pair<string, string> p = names[A];
			q[x].push(names[A]);
			qidx[p.first] = qidx[p.second] = x;
		} else if (op == 3) {
			scanf("%d", &x);
			if (q[x].size() > 0) {
				pair<string, string> p = q[x].front();
				q[x].pop();
				qidx[p.first] = qidx[p.second] = 0;
			}
		} else if (op == 4) {
			scanf("%d", &x);
			if (q[x].size() == 0)
				printf("-1\n");
			else {
				v.clear();
				while (q[x].size() > 0) {
					pair<string, string> p = q[x].front();
					q[x].pop();
					v.push_back(p);
				}

				int first = 1;
				for (i = (int) (v.size()) - 1; i >= 0; i--) {
					const pair<string, string>& p = v[i];
					if (!first) printf(" ");
					printf("%s %s", p.first.c_str(), p.second.c_str());
					first = 0;
				}
				printf("\n");

				for (i = 0; i < v.size(); i++)
					q[x].push(v[i]);
			}
		} else if (op == 5) {
			scanf("%s", A);
			x = qidx[A];
			if (x == 0)
				printf("-1\n");
			else
				printf("%d\n", x);
		}
	}

	return 0;
}