#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <cassert>
#include <cstdlib>
#include <ctime>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <bitset>
#include <string>
#define pii pair <int, int>
#define pdd pair <double, double>
#define x first
#define y second
#define mp make_pair
#define pb push_back
#define INF 1000000005
#define NMAX 205
using namespace std;
int n, m, t;
pair <string, string> A[NMAX];
map <string, int> H;
int H2[NMAX];
queue <int> G[NMAX];
int open[NMAX];

void remove(int idx)
{
	while (G[idx].size())
	{
		int node = G[idx].front();
		H2[node] = -1;
		G[idx].pop();
	}
}

void print(int idx)
{
	if (G[idx].size() == 0)
	{
		cout << "-1\n";
		return ;
	}
	
	vector <int> st;
	while (G[idx].size())
	{
		int node = G[idx].front();
		st.pb(node);
		G[idx].pop();
	}
	
	for (int i = st.size() - 1; i >= 0; i--)
	{
		cout << A[st[i]].x << " " << A[st[i]].y;
		if (i > 0)
			cout << " ";
	}
	cout << "\n";
	
	for (int i = 0; i < st.size(); i++)
		G[idx].push(st[i]);
}
 
int main()
{
    //~ freopen("input", "r", stdin);
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
		cin >> A[i].x >> A[i].y;
		H[A[i].x] = i;
		H[A[i].y] = i;
    }
    
    cin >> t;
    int type, x, y;
    string name;
    for (int i = 1; i <= t; i++)
    {
		cin >> type;
		switch (type)
		{
			case 1: cin >> x;
					open[x] ^= 1;
					if (open[x] == 0)
						remove(x);
					break ;
					
			case 2: cin >> x >> name;
					G[x].push(H[name]);
					H2[H[name]] = x;
					break ;
					
			case 3: cin >> x;
					y = G[x].front();
					H2[y] = -1;
					G[x].pop();
					break ;
			
			case 4: cin >> x;
					print(x);
					break ;
			
			case 5: cin >> name;
					cout << H2[H[name]] << "\n";
					break ;
		}	
    }
    return 0;
}