#pragma GCC optimize(3,"Ofast","inline","unroll-loops")
#include<bits/stdc++.h>
using namespace std;
using i64=long long;
namespace aimat{
char *p1,p2,buf[100010],obuf[100010],p3=obuf;
#define gc() (p1p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1p2)?EOF:p1++)
#define pc(x) (p3obuf+100000&&fwrite(p3=obuf,1,100000,stdout),*p3++=x)
int read(){
int x=0;
char c=gc();
while(c<48)c=gc();
while(47<c)x=(x<<3)+(x<<1)+(c&15),c=gc();
return x;
}
void write(int x){
if(9<x)write(x/10);
pc(x%10|48);
}
} using namespace aimat;
const int N=200010;
vector<int>adj[N];
bitset<N/2>go[N/2];
int bel1[N],bel2[N];
const int B1=500,B2=10000;
bitset<N/2>b1[N/B1/2+2],b2[N/B2/2+2];
int a[N],b[N],ida[N],idb[N];
signed main(){
// cin.tie(0)->sync_with_stdio(false);
// cout<<fixed<<setprecision(15);
int c=read(),T=read();
while(T--){
int n=read(),m=read(),q=read();
for_each(adj+1,adj+n+1,[&](auto &x){x.clear();});
for(int i=0;i<m;++i){int a=read(),b=read();adj[a].emplace_back(b);}
for(int i=1;i<=n;++i)go[i]=0,go[i].set(i);
for(int i=1;i<=n;++i)a[i]=read(),ida[a[i]]=i;
for(int i=1;i<=n;++i)b[i]=read(),idb[b[i]]=i;
for(int i=n;i;--i)for(int &j:adj[i])go[i]|=go[j];
for(int i=1;i<=n+1;++i)bel1[i]=(i-1)/B1+1,bel2[i]=(i-1)/B2+1;
for(int i=0;i<=bel1[n]+1;++i)b1[i]=0;for(int i=0;i<=bel2[n]+1;++i)b2[i]=0;
for(int i=1;i<=n;++i)b1[bel1[a[i]]].set(i),b2[bel2[b[i]]].set(i);
for(int i=bel1[n]-1;i;--i)b1[i]|=b1[i+1];
for(int i=bel2[n]-1;i;--i)b2[i]|=b2[i+1];
while(q--){
int o=read();
if(o1){
int x=read(),y=read();
for(int i=1;i<=bel1[a[x]];++i)b1[i][x]=0;
for(int i=1;i<=bel1[a[y]];++i)b1[i][x]=1;
for(int i=1;i<=bel1[a[y]];++i)b1[i][y]=0;
for(int i=1;i<=bel1[a[x]];++i)b1[i][y]=1;
swap(ida[a[x]],ida[a[y]]),swap(a[x],a[y]);
}else if(o==2){
int x=read(),y=read();
for(int i=1;i<=bel2[b[x]];++i)b2[i][x]=0;
for(int i=1;i<=bel2[b[y]];++i)b2[i][x]=1;
for(int i=1;i<=bel2[b[y]];++i)b2[i][y]=0;
for(int i=1;i<=bel2[b[x]];++i)b2[i][y]=1;
swap(idb[b[x]],idb[b[y]]),swap(b[x],b[y]);
}else{
int x=read(),l=read(),r=read();
bitset<N/2>now=b1[bel1[l]+1];
for(int i=l;i<=min(n,B1bel1[l]);++i)now.set(ida[i]);
if(bel1[n]!=bel1[r+1])now^=b1[bel1[r+1]+1];
for(int i=r+1;i<=min(n,B1bel1[r+1]);++i)now[ida[i]]=now[ida[i]]^1;
int ok=0;auto nw=now&go[x];
for(int i=bel2[n];i;--i)
if((nw&b2[i]).size()){
for(int j=min(B2i,n);j>=(i-1)*B2+1;--j)
if(nw[idb[j]]){
cout<<j<<'\n';
ok=1;goto label;
}
}
label:;
if(!ok)cout<<"0\n";
}
}
}
}
