#include <cstdio>
#include <queue>
#include <cstring>
#include <vector>
#include <algorithm>

#define NMAX 10007
#define LMAX 20007

using namespace std;

char a[NMAX][LMAX], b[NMAX][LMAX], c[LMAX];
bool Ap[NMAX];
queue< int > List[NMAX], q;
vector< int > H;
int n, m, T, Tip, x, Ans, Sol;

inline int Find(char c[NMAX]){
    Ans = 0;
    for(int i = 1; i <= m; ++i){
        int L = strlen(a[i]);
        int L2 = strlen(c);
        Ans = i;
        for(int j = 0; j < max(L, L2); ++j)
            if(a[i][j] != c[j]){
                Ans = 0;
                break;
            }
        if(Ans == i)
            return i;
        L = strlen(b[i]);
        Ans = i;
        for(int j = 0; j < max(L, L2); ++j)
            if(b[i][j] != c[j]){
                Ans = 0;
                break;
            }
        if(Ans == i)
            return i;
    }
    return 0;
}

int main(){
    ///freopen("a.in", "r", stdin);
    scanf("%d %d\n", &n, &m);
    for(int i = 1; i <= m; ++i)
        scanf("%s %s\n", a[i], b[i]);
    for(scanf("%d", &T); T > 0; --T){
        scanf("%d", &Tip);
        if(Tip < 5)
            scanf("%d", &x);
        if(Tip == 1)
            Ap[x] = !Ap[x];
        if(Tip == 2){
            memset(c, 0, sizeof(c));
            scanf("%s", c);
            Ans = Find(c);
            List[x].push(Ans);
        }
        if(Tip == 3)
            List[x].pop();
        if(Tip == 4){
            H.clear();
            while(!List[x].empty()){
                int Nod = List[x].front();
                q.push(Nod);
                H.push_back(Nod);
                List[x].pop();
            }
            while(!q.empty()){
                int Nod = q.front();
                List[x].push(Nod);
                q.pop();
            }
            reverse(H.begin(), H.end());
            if(H.size() > 1){
                printf("%s %s", a[H[0]], b[H[0]]);
                for(int i = 1; i < H.size(); ++i)
                    printf(" %s %s", a[H[i]], b[H[i]]);
                printf("\n");
            }
            else
                printf("-1\n");
        }
        if(Tip == 5){
            memset(c, 0, sizeof(c));
            scanf("%s", &c);
            Ans = Find(c);
            Sol = -1;
            for(int i = 1; i <= n && Sol == -1; ++i)
                if(Ap[i] == 1){
                    int l = 0;
                    while(!List[i].empty()){
                        int Nod = List[i].front();
                        ++l;
                        q.push(Nod);
                        List[i].pop();
                    }
                    int Nr = 0;
                    while(!q.empty()){
                        int Nod = q.front();
                        List[i].push(Nod);
                        ++Nr;
                        if(Nod == Ans)
                            Sol = l - Nr + 1;
                        q.pop();
                    }
                }
            printf("%d\n", Sol);
        }
    }
    return 0;
}