我常常追忆过去。
生命瞬间定格在脑海。我将背后的时间裁剪、折叠、蜷曲，揉捻成天上朵朵白云。
云朵之间亦有分别：积云厚重，而卷云飘渺。生命里震撼的场景掠过我的思绪便一生无法忘怀，而更为普通平常的记忆在时间的冲刷下只留下些许残骸。追忆宛如入梦，太过清楚则无法愉悦自己的幻想，过分模糊却又坠入虚无。只有薄雾间的山水，面纱下的女子，那恰到好处的朦胧，才能满足我对美的苛求。
追忆总在不经意间将我裹进泛黄的纸页里。分别又重聚的朋友，推倒又重建的街道，种种线索协助着我从一个具体的时刻出发沿时间的河逆流而上。曾经的日子无法重来，我只不过是一个过客。但我仍然渴望在每一次追忆之旅中留下闲暇时间，在一个场景前驻足，在岁月的朦胧里瞭望过去的自己，感受尽可能多的甜蜜。美好的时光曾流过我的身体，我便心满意足。
过去已经凝固，我带着回忆向前，只是时常疏于保管，回忆也在改变着各自的形态。这给我的追忆旅程带来些许挑战。
我该在哪里停留？我问我自己。
厉害了。
省选的时候被这题爆了。
然后发现很厉害。
其实要去在 $a_i,b_i$ 上分块， $a_i$ 和图都能堪称限制塞进 bitset 里（听说这个在 dag 上的 trick 是典的），这时候发现直接做是出现不了 $\omega$ 的，那就想办法，比如在 $a_i$ 上分块，先找块再找块内都能用 bitset 做，然后就是除以了一个 $\omega$。
但我的确是对题目背景有一些感触（考场上直接跳掉了）。题目背景似乎是在追求美好的回忆，实则对追忆做了探讨与平衡，想到自己也总是会被坠入回忆，沉溺得越深，再清醒就会越惊恐，脊背发凉。我的回忆的景象也许有点奇怪。午后被微风吹起的窗帘、远眺的港口、……我很好奇它们是怎么被留住的，要说“美的苛求”，倒不如说是一本笔记的封面……拿起来就不舍得放下，看着封面也能陷入追忆……
#include<bits/stdc++.h>
#define reg register
#define rint reg int
#define rep(i,a,b) for(rint i=a;i<=b;++i)
#define drep(i,a,b) for(rint i=a;i>=b;--i)
using ll=long long;
using ull=unsigned ll;
#define pb push_back
#define eb emplace_back
#define ins insert
#define elif(A) else if(A)
using namespace std;
const int N=1e5+10,B=8000,MAXN=N/B+10,M=2e5+10;
vector<int>e[N];
bitset<N>G[N],ba[MAXN],bb[MAXN];
int cnt;
int L[MAXN],R[MAXN],rev[N];
int a[N],arv[N],b[N],brv[N];
bitset<N>ans;
void __SOLVE__(){
rint n,m,q;
read(n);read(m);read(q);
rep(i,1,n)e[i].clear();
rep(i,1,m){rint u,v;read(u);read(v);e[u].eb(v);}
drep(i,n,1){G[i].reset(),G[i][i]=1;for(auto to:e[i])G[i]|=G[to];}
cnt=(n-1)/B+1;
rep(i,1,n){rev[i]=(i-1)/B+1;if(!L[rev[i]])L[rev[i]]=i;R[rev[i]]=i;}
rep(i,0,cnt)ba[i].reset(),bb[i].reset();
rep(i,1,n)read(a[i]),arv[a[i]]=i,ba[rev[a[i]]][i]=1;
rep(i,1,n)read(b[i]),brv[b[i]]=i,bb[rev[b[i]]][i]=1;
while(q--){
rint op;
read(op);
if(op==1){
rint x,y;
read(x);
read(y);
ba[rev[a[x]]][x]=0;
ba[rev[a[y]]][y]=0;
swap(arv[a[x]],arv[a[y]]);
swap(a[x],a[y]);
ba[rev[a[x]]][x]=1;
ba[rev[a[y]]][y]=1;
}elif(op==2){
rint x,y;
read(x);
read(y);
bb[rev[b[x]]][x]=0;
bb[rev[b[y]]][y]=0;
swap(brv[b[x]],brv[b[y]]);
swap(b[x],b[y]);
bb[rev[b[x]]][x]=1;
bb[rev[b[y]]][y]=1;
}else{
rint x,l,r;
read(x);read(l);read(r);
ans=0;
if(rev[l]==rev[r])rep(i,l,r)ans[arv[i]]=1;
else {
rep(i,l,R[rev[l]])ans[arv[i]]=1;
rep(i,L[rev[r]],r)ans[arv[i]]=1;
rep(i,rev[l]+1,rev[r]-1)ans|=ba[i];
}
ans&=G[x];
if(!ans.any()){
write(0,'\n');
continue;
}
rint fd=-1;
drep(t,cnt,1){
if((ans&bb[t]).any()){
fd=t;
break;
}
}
drep(i,R[fd],L[fd]){
if(ans[brv[i]]){
write(i,'\n');
break;
}
}
}
}
}
signed main(){
rint c,t;
read(c);
read(t);
while(t--)__SOLVE__();
return 0;
}