D. Cross Coloring

很容易想到的就是分成几个块 有几个就是k多少次幂
但是显然暴力的做法是n2的 我们考虑如何优化
我们考虑对每一行 这个x[i]能成立的条件是啥 那就是y[i]里有比他更小的即可
对于列也是如此
最后要注意的就是要特判0的情况

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+20;
const int M = 998244353;
const int mod = 998244353;
#define int long long
#define endl '\n'
#define Endl '\n'
#define YES cout<<"YES"<<endl;
#define NO cout<<"NO"<<endl;
#define _ 0
#define inf 0x3f3f3f3f3f3f3f3f
#define fast ios::sync_with_stdio(false);cin.tie(nullptr);
int qpow(int a,int k,int p){
    int res=1;
    while(k){
        if(k&1)res=res*a%p;
        k>>=1;
        a=a*a%p;
    }
    return res;
}
void solve() {
    int n,m,k,q;cin>>n>>m>>k>>q;
    map<int,int>mpx,mpy;
    for(int i=1;i<=q;i++){
        int x,y;cin>>x>>y;
        mpx[x]=i;
        mpy[y]=i;
    }
    set<int>s;
    int mn1=inf,mn2=inf;
    for(auto i:mpx)mn1=min(mn1,i.second);
    for(auto i:mpy)mn2=min(mn2,i.second);
    if(mpx.size()!=n)mn1=0;
    if(mpy.size()!=m)mn2=0;
    for(auto i:mpx){
        if(i.second>=mn2)s.insert(i.second);
    }
    for(auto i:mpy){
        if(i.second>=mn1)s.insert(i.second);
    }
    cout<<qpow(k,s.size(),mod)<<endl;
}
signed main(){
    fast
    int T;cin>>T;
    while(T--) {
        solve();
    }
    return ~~(0^_^0);
}