#include<bits/stdc++.h>
using namespace std;
int n,m,q;
vector<int> e[100010];
int a[100010],b[100010];
int wha[100010],whb[100010];
const int lim=64;
bitset<100010> bit[100010],tree1[lim*2],tree2[lim*2];
void upd1(int now,int l,int r,int qx,int qz1,int qz2)
{
    tree1[now][qz1]=qz2;
    if(l==r || now>=lim) return;
    int mid=l+r>>1;
    if(qx<=mid) upd1(now<<1,l,mid,qx,qz1,qz2);
    else upd1(now<<1|1,mid+1,r,qx,qz1,qz2);
}
void upd2(int now,int l,int r,int qx,int qz1,int qz2)
{
    tree2[now][qz1]=qz2;
    if(l==r || now>=lim) return;
    int mid=l+r>>1;
    if(qx<=mid) upd2(now<<1,l,mid,qx,qz1,qz2);
    else upd2(now<<1|1,mid+1,r,qx,qz1,qz2);
}
bitset<100010> nowbit[2];
void get_bit(int now,int l,int r,int qx,int op)
{
    if(now>=lim || l==r)
    {
        for(int i=l; i<=qx; ++i) nowbit[op][wha[i]]=1;
        return;
    }
    int mid=l+r>>1;
    if(qx<=mid) get_bit(now<<1,l,mid,qx,op);
    else nowbit[op]|=tree1[now<<1],get_bit(now<<1|1,mid+1,r,qx,op);
}
int dfs(int now,int l,int r,int qx,int ql,int qr)
{
    if(now>=lim || l==r)
    {
        int ans=r;
        while(ans>=l && (!nowbit[1][whb[ans]] || !bit[qx][whb[ans]])) --ans;
        return ans<l?0:ans;
    }
    int mid=l+r>>1;
    if((bit[qx]&tree2[now<<1|1]&nowbit[1]).any()) return dfs(now<<1|1,mid+1,r,qx,ql,qr);
    else return dfs(now<<1,l,mid,qx,ql,qr);
}
int main()
{
    freopen("recall.in","r",stdin);
    freopen("recall.out","w",stdout);
    ios::sync_with_stdio(false),cin.tie(0);
    int testid,t; cin>>testid>>t; while(t--)
    {
        cin>>n>>m>>q;
        for(int i=1; i<=n; ++i) e[i].clear();
        for(int i=1; i<=m; ++i)
        {
            int u,v; cin>>u>>v;
            e[u].push_back(v);
        }
        for(int i=1; i<=n; ++i) cin>>a[i];
        for(int i=1; i<=n; ++i) cin>>b[i];
        for(int i=n; i>=1; --i)
        {
            bit[i].reset(),bit[i][i]=1;
            for(int j:e[i]) bit[i]|=bit[j];
        }
        for(int i=1; i<2*lim; ++i) tree1[i].reset(),tree2[i].reset();
        for(int i=1; i<=n; ++i)
        {
            upd1(1,1,n,a[i],i,1),upd2(1,1,n,b[i],i,1);
            wha[a[i]]=i,whb[b[i]]=i;
        }
        while(q--)
        {
            int op,x,y,l,r; cin>>op;
            if(op==1)
            {
                cin>>x>>y;
                upd1(1,1,n,a[x],x,0),upd1(1,1,n,a[y],y,0);
                upd1(1,1,n,a[x],y,1),upd1(1,1,n,a[y],x,1);
                swap(wha[a[x]],wha[a[y]]);
                swap(a[x],a[y]);
            }
            if(op==2)
            {
                cin>>x>>y;
                upd2(1,1,n,b[x],x,0),upd2(1,1,n,b[y],y,0);
                upd2(1,1,n,b[x],y,1),upd2(1,1,n,b[y],x,1);
                swap(whb[b[x]],whb[b[y]]);
                swap(b[x],b[y]);
            }
            if(op==3)
            {
                cin>>x>>l>>r;
                nowbit[0].reset(),nowbit[1].reset();
                get_bit(1,1,n,l-1,0),get_bit(1,1,n,r,1);
                nowbit[1]^=nowbit[0];
                cout<<dfs(1,1,n,x,l,r)<<'\n';
            }
        }
    }
    return 0;
}