#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,M=2e5+5,K=316;
int c,T;
int n,m,q,qq[N],a[N],b[N],aa[N],bb[N];
int hd[N],nex[M],to[M],deg[N],psz;
bitset<N>can[N],cur;
struct fenkuai{
	bitset<N>p[K+5];//我写的是前缀和，不知道有没有问题
    inline void clear(){
        for(int i=0;i<=n/K;i++)p[i]=0;
    }
	inline void update(int x,int y){
		for(int i=y/K;i<=n/K;i++)p[i][x]=p[i][x]^1;
	}
}A,B;
inline void adde(int u,int v){
	psz++,nex[psz]=hd[u],to[psz]=v,hd[u]=psz,deg[v]++;
}
inline void solve(){
	cin>>n>>m>>q;psz=0;
	for(int i=1;i<=n;i++)hd[i]=deg[i]=0,can[i]=0,can[i][i]=1;
    A.clear(),B.clear();
	while(m--){
		int u,v;cin>>u>>v;
		adde(v,u);
	}
	int l=1,r=0;
	for(int i=1;i<=n;i++){
		if(!deg[i])qq[++r]=i;
	}
	while(l<=r){
		int u=qq[l++];
		for(int i=hd[u];i;i=nex[i]){
			int v=to[i];
			can[v]|=can[u];
			if(!--deg[v])qq[++r]=v;
		}
	}//图连通性
	for(int i=1;i<=n;i++)cin>>a[i],aa[a[i]]=i;
	for(int i=1;i<=n;i++)cin>>b[i],bb[b[i]]=i;
	for(int i=1;i<=n;i++)A.p[a[i]/K][i]=1,B.p[b[i]/K][i]=1;
    for(int i=1;i<=n/K;i++)A.p[i]|=A.p[i-1],B.p[i]|=B.p[i-1];
	while(q--){
		int o,x,y,l,r;cin>>o>>x;
		if(o==1){
			cin>>y;
			A.update(x,a[x]),A.update(x,a[y]);
			A.update(y,a[y]),A.update(y,a[x]);
			swap(aa[a[x]],aa[a[y]]),swap(a[x],a[y]);
		}else if(o==2){
			cin>>y;
			B.update(x,b[x]),B.update(x,b[y]);
			B.update(y,b[y]),B.update(y,b[x]);
			swap(bb[b[x]],bb[b[y]]),swap(b[x],b[y]);
		}else{
			cin>>l>>r;
			if(r/K-l/K<2){
				cur=0;
				for(int i=l;i<=r;i++)cur[aa[i]]=1;
			}else{
				cur=A.p[r/K-1]^A.p[l/K];
				for(int i=l;i<=(l/K+1)*K-1;i++)cur[aa[i]]=1;
				for(int i=r/K*K;i<=r;i++)cur[aa[i]]=1;
			}
			cur&=can[x];
            int fl=0;
			for(int i=n/K;i>=0;i--){//暴力枚举块
                if(fl)break;
				if((i==0&&(B.p[i]&cur)!=0)||(i!=0&&((B.p[i]^B.p[i-1])&cur)!=0)){
					for(int j=min((i+1)*K-1,n);j>=i*K;j--){//暴力枚举块内的数
						if(cur[bb[j]]!=0){
                            cout<<j<<'\n',fl=1;break;
                        }
					}
				}
			}
            if(!fl)cout<<0<<'\n';
		}
	}
}
int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>c>>T;
	while(T--)solve();
}