QWQ,求条，悬二关

#include<bits/stdc++.h>
#define ui unsigned int
using namespace std;
int n,p;
ui SA,SB,SC;
int s;
vector<int>g[(int)2e5+10];
ui rng61(){
	SA ^= SA << 16;
	SA ^= SA >> 5;
	SA ^= SA << 1;
	ui t = SA;
	SA = SB;
	SB = SC;
	SC ^= t ^ SA;
	return SC;
}
void addedge(int x,int y){
    g[y].push_back(x);
    g[x].push_back(y);
}
struct node{
    int l,r,id,lcaa;
}q[(int)2e5+10];
map<int,int>mp;
int a[(int)2e5+10],m;
int fa[(int)2e5+10][25];
int ord[(int)4e5+10];
int cntt[(int)2e5+10];
int idx,cnt,ans;
int st[(int)2e5+10];
int b[(int)2e5+10];
int ed[(int)2e5+10];
int dep[(int)2e5+10];
int res[(int)2e5+10];
int id[(int)2e5+10];
int cnt2[(int)2e5+10];
void add(int x){
   cntt[ord[x]]++;
    if(cntt[ord[x]]==1){
        ++cnt2[a[ord[x]]];
        if(cnt2[a[ord[x]]]==1)ans++;
    }
    if(cntt[ord[x]]==2){
        cnt2[a[ord[x]]]--;
        if(cnt2[a[ord[x]]]==0)ans--;
    }
}
void sub(int x){
    cntt[ord[x]]--;
    if(cntt[ord[x]]==1){
        ++cnt2[a[ord[x]]];
        if(cnt2[a[ord[x]]]==1)ans++;
    }
    if(cntt[ord[x]]==0){
        cnt2[a[ord[x]]]--;
        if(cnt2[a[ord[x]]]==0)ans--;
    }
}
void dfs(int x,int faa){
    ord[++idx]=x;
    st[x]=idx;
    for(int i=0;i<g[x].size();i++){
        int y=g[x][i];
        if(y==faa)continue;
        dep[y]=dep[x]+1;
        fa[y][0]=x;
        dfs(y,x);
    }
    ord[++idx]=x;
    ed[x]=idx;
}
int lca(int x,int y){
    if(dep[x]<dep[y])swap(x,y);
    for(int i=20;i>=0;i--){
        if(dep[fa[x][i]]>=dep[y]){
            x=fa[x][i];
        }
    }
    if(x==y)return x;
    for(int i=20;i>=0;i--){
        if(fa[x][i]!=fa[y][i]){
            x=fa[x][i],y=fa[y][i];
        }
    }
    return fa[x][0];
}
bool cmp(node x,node y){
    if(id[x.l]!=id[y.l])return id[x.l]<id[y.l];
    return x.r<y.r;
}
void solve(){
	scanf("%d%d%u%u%u", &n, &p, &SA, &SB, &SC);
    s=sqrt(2*n);
	for(int i = 2; i <= p; i++)
	addedge(i - 1, i);
	for(int i = p + 1; i <= n; i++){
	addedge((rng61() % (ui)(i-1))+(ui)1, i);
    }
    for(int i=1;i<=2*n;i++)id[i]=(i-1)/s+1;
	for(int i = 1; i <= n; i++)
	a[i] = (int)((rng61() % (ui)(n)) + 1),b[i]=a[i];
    sort(b+1,b+n+1);
    int len=unique(b+1,b+n+1)-(b+1);
    for(int i=1;i<=n;i++){
        a[i]=lower_bound(b+1,b+len+1,a[i])-b;
    }
    cin>>m;
    dep[0]=-1;
    dfs(1,0);
    for(int i=1;i<=20;i++){
        for(int j=1;j<=n;j++){
            fa[j][i]=fa[fa[j][i-1]][i-1];
        }
    }
    int js=0;
    for(int i=1;i<=m;i++){
        int op,x,y;
        cin>>op>>x>>y;;
        if(op!=1)continue;
        js++;
        q[js].id=js;
        if(st[x]>st[y])swap(x,y);
        if(lca(x,y)==x||lca(x,y)==y)q[js].l=st[x],q[js].r=st[y];
        if(lca(x,y)!=x&&lca(x,y)!=y)q[js].l=min(ed[x],st[y]),q[js].r=max(st[y],ed[x]),q[js].lcaa=lca(x,y);
    }
    sort(q+1,q+js+1,cmp);
    int l=1,r=0;
    ans=0;
    for(int i=1;i<=js;i++){
        while(l<q[i].l)sub(l++);
        while(l>q[i].l)add(--l);
        while(r<q[i].r)add(++r);
        while(r>q[i].r)sub(r--);
        if(q[i].lcaa){
            add(st[q[i].lcaa]);
        }
        res[q[i].id]=ans;
        if(q[i].lcaa){
            sub(st[q[i].lcaa]);
        }
}
    for(int i=1;i<=js;i++)cout<<res[i]<<'\n';
    for(int i=1;i<=n;i++){
        g[i].clear();
        cntt[i]=0;
        cnt2[a[i]]=0;
        st[i]=0,ed[i]=0;
    }
    for(int i=0;i<=20;i++){
        for(int j=1;j<=n;j++)fa[j][i]=0;
    }
    idx=0;
}
signed main(){
    int t;
    cin>>t;
    while(t--){
       solve();
    }
    return 0;
}