s=raw_input("")
prop=s.split(" ")
n=int(prop[0])
m=int(prop[1])
counter=[]
for i in range(0,n+1):
    counter.append(0)
persons=[]
for i in range(0,n+1):
    persons.append([])
name=[]
surname=[]
for i in range(0,m):
    s=raw_input("")
    prop=s.split(" ")
    name.append(prop[0])
    surname.append(prop[1])
t=int(raw_input(""))
for i in range(0,t):
    s=raw_input("")
    prop=s.split(" ")
    command=int(prop[0])
    if command==1:
        if counter[int(prop[1])]==0:
            counter[int(prop[1])]=1
        else:
            counter[int(prop[1])]=0
            persons[int(prop[1])]=[]
    elif command==2:
        persons[int(prop[1])].append(prop[2])
    elif command==3:
        persons[int(prop[1])].pop(0)
    elif command==4:
        if len(persons[int(prop[1])])==0:
            print -1
        else:
            s=""
            for i in range(len(persons[int(prop[1])])-1,-1,-1):
                nev=persons[int(prop[1])][i]
                if nev in name:
                    s=s+nev+" "+surname[name.index(nev)]+" "
                else:
                    s=s+name[surname.index(nev)]+" "+nev+" "
            s=s[:-1]
            print s
    else:
        nev1=""
        nev2=""
        if prop[1] in name:
            nev1=prop[1]
            nev2=surname[name.index(prop[1])]
        else:
            nev1=name[surname.index(prop[1])]
            nev2=prop[1]
        i=0
        p=0
        while (i<=n) and (p==0):
            if (nev1 in persons[i]) or (nev2 in persons[i]):
                print i
                p=1
            i=i+1
        if i>n:
            print -1