题面传送门
奇妙的被强制套上LCT的二合一。
首先考虑加边怎么做。看到仙人掌想到建圆方树，由于强制在线考虑用LCT维护。每次加入先看路径上有没有方点，如果有则不能加入，如果没有则看有没有成环，如果不成环直接加入，否则将环断开并新建立方点，并将环上所有点连向方点。就可以维护加边操作。
然后考虑询问。因为这是仙人掌，所以期望可以表示成\(E(点)-E(边)+E(环)\)，由期望的线性性可知这是成立的。
\(E(点)\)为显然为\(1\)，\(E(白点)\)为\((\frac{n-1}{n})^k\)
\(E(白边)\)为\((\frac{n-2}{n})^k\)，\(E(黑边)\)为\(1-(\frac{n-1}{n})^k+(\frac{n-2}{n})^k\)
设环长度为\(Len\)，则\(E(白环)\)为\(\frac{n-Len}{n}\),\(E(黑环)\)直接算比较难算，考虑容斥。
枚举至少有\(x\)个白点，乘上容斥系数\((-1)^k\),得到\(E(黑环)=\sum\limits_{i=0}^{Len}{(-1)^iC_{Len}^{i}(\frac{n-i}{n})^k}\)
时间复杂度为\(\sum\limits{Len\log p}\)，即\(q\log p\)
总时间复杂度为\(O(q(\log n+\log p))\)
code:

#include<bits/stdc++.h>
#define I inline
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define abs(x) ((x)>0?(x):-(x))
#define re register
#define RI re int
#define ll long long
#define db double
#define lb long db
#define N 200000
#define K 500
#define mod 998244353
#define Mod (mod-1)
#define eps (1e-5)
#define U unsigned int
#define it iterator
#define Gc() getchar() 
#define Me(x,y) memset(x,y,sizeof(x))
#define d(x,y) (m*x+(y))
#define R(n) (rand()*rand()%(n)+1)
#define Pc(x) putchar(x)
using namespace std;
int n,m,k,w,z,Ls,d[N+5],x,y,Len;ll Ans,frc[N+5],Inv[N+5],In,La;
I ll mpow(ll x,int y=mod-2){ll Ans=1;while(y) y&1&&(Ans=Ans*x%mod),y>>=1,x=x*x%mod;return Ans;}I ll C(int x,int y){return frc[x]*Inv[y]%mod*Inv[x-y]%mod;}
namespace LCT{
	int l[N+5],r[N+5],Fl[N+5],F[N+5],S[N+5],fa[N+5],st[N+5],H,cnt,ST[N+5],Sh;I int RS(int x){return r[fa[x]]==x;}I int CD(int x){return r[fa[x]]==x||l[fa[x]]==x;}
	I void Up(int x){S[x]=F[x]|S[l[x]]|S[r[x]];}I void PF(int x){x&&(swap(l[x],r[x]),Fl[x]^=1);}I void P(int x){Fl[x]&&(PF(l[x]),PF(r[x]),Fl[x]=0);}
	I void RO(int x){int y=fa[x],z=fa[y],b=(RS(x)?l[x]:r[x]);CD(y)&&((RS(y)?r[z]:l[z])=x);RS(x)?(l[x]=y,r[y]=b):(r[x]=y,l[y]=b);fa[x]=z;fa[y]=x;b&&(fa[b]=y);Up(y);Up(x);}
	I void SP(int x){int y=x;st[H=1]=x;while(CD(y)) st[++H]=y=fa[y];;while(H) P(st[H--]);while(CD(x)) CD(fa[x])&&(RO(RS(x)^RS(fa[x])?x:fa[x]),0),RO(x);}
	I void AC(int x){for(int y=0;x;x=fa[y=x]) SP(x),r[x]=y,Up(x);}I int FR(int x){AC(x);SP(x);while(l[x]) P(x),x=l[x];return SP(x),x;}
	I void MR(int x){AC(x);SP(x);PF(x);}I void SL(int x,int y){MR(x);AC(y);SP(y);}I void LK(int x,int y){MR(x);fa[x]=y;}I void CT(int x,int y){SL(x,y);if(fa[x]^y||l[y]^x) exit(0);l[y]=fa[x]=0;Up(y);}
	I void DFS(int x){if(!x) return;P(x);DFS(l[x]);ST[++Sh]=x;DFS(r[x]);}I void DC(int x,int y){Sh=-1;SL(x,y);DFS(y);for(RI i=0;i<Sh;i++) CT(ST[i],ST[i+1]);F[++cnt]=1;for(RI i=0;i<=Sh;i++) LK(cnt,ST[i]);Len=Sh+1;}
}
int main(){
	freopen("graph.in","r",stdin);freopen("graph.out","w",stdout);
	RI i,j;scanf("%d%d%d%d",&n,&m,&k,&w);LCT::cnt=n;In=mpow(n);Ans=(w?n:n*mpow((n-1)*In%mod,k)%mod);for(frc[0]=Inv[0]=i=1;i<=n;i++) frc[i]=frc[i-1]*i%mod,Inv[i]=mpow(frc[i]);
	while(m--){
		scanf("%d%d",&x,&y);/*x^=La;y^=La;*///if(x==y) {printf("%lld\n",La=Ans);continue;}
		if(LCT::FR(x)^LCT::FR(y)){LCT::LK(x,y),Ans-=mpow((n-2)*In%mod,k)+w*(1-2*(mpow((n-1)*In%mod,k))+mpow((n-2)*In%mod,k));Ans=(Ans%mod+mod)%mod;printf("%lld\n",La=Ans);continue;}
		LCT::SL(x,y);if(LCT::S[y]) {printf("%lld\n",La=Ans);continue;}Ans-=mpow((n-2)*In%mod,k)+w*(1-2*(mpow((n-1)*In%mod,k))+mpow((n-2)*In%mod,k));
		LCT::DC(x,y);/*cerr<<Len<<'\n';*/Ans+=mpow((n-Len)*In%mod,k);if(w) for(j=0;j<=Len;j++) Ans+=(j&1?-1:1)*C(Len,j)*mpow((n-j)*In%mod,k)%mod;Ans=(Ans%mod+mod)%mod;printf("%lld\n",La=Ans);
	}
}