#include <iostream>
#include <cstring>
#include <vector>
#include <unordered_map>
#include <fstream>

using namespace std;

pair<string,string> names[104];
vector <int> G[104];
unordered_map <string, int> MAP;
unordered_map <string, int> indexed;

int N, M, T;

int main()
{
    ///ifstream cin("date.in");

    cin >> N >> M;

    for ( int i = 1; i <= M; ++i )
    {
        cin >> names[i].first >> names[i].second;

        MAP[ names[i].first ] = i;
        MAP[ names[i].second ] = i;
    }

    cin >> T;

    int tip, x;
    string name;

    while ( T-- )
    {
        cin >> tip;

        if ( tip == 1 )
        {
            cin >> x;

            if ( G[x].size() == 0 ) continue;

            for ( vector<int>::iterator it = G[x].begin(); it != G[x].end(); ++it )
                    indexed[ names[*it].first ] = 0,
                    indexed[ names[*it].second ] = 0;

            G[x].clear();
        }

        if ( tip == 2 )
        {
            cin >> x >> name;

            G[x].push_back( MAP[ name ] );

            indexed[ names[ MAP[name] ].first ] = x;
            indexed[ names[ MAP[name] ].second ] = x;
        }

        if ( tip == 3 )
        {
            cin >> x;

            if ( G[x].size() == 0 ) continue;

            indexed[ names[ *G[x].begin() ].first ] = 0;
            indexed[ names[ *G[x].begin() ].second ] = 0;

            G[x].erase( G[x].begin() );
        }

        if ( tip == 4 )
        {
            cin >> x;

            if ( G[x].size() == 0 )
                    cout << "-1";
            else
            {
                for ( vector<int>::reverse_iterator it = G[x].rbegin(); it != G[x].rend(); ++it )
                {
                    cout << names[*it].first << " " << names[*it].second << " ";
                }
            }

            cout << "\n";
        }

        if ( tip == 5 )
        {
            cin >> name;

            if ( indexed[name] != 0 )
                    cout << indexed[name] << "\n";
            else
                    cout << "-1\n";
        }
    }

    return 0;
}