感觉是这次金组最好的题了吧（

T1 T2 都挺板子的

首先先看银组的弱化版（少了时间限制 $m$）

考虑每 $k$ 轮每个点都到哪里了

设 $k$ 轮后 $i$ 到达了 $p_i$，经过点的集合为 $s_i$

发现所有 $i\to p_i$ 的边组成了若干个环（每个店入度出度均为 1）

而一个点 $i$ 能到达的点集即为 $i$ 所在的环上所有 $s_i$ 的并集，于是遍历每个环，然后暴力合并即可

由于一共交换 $k$ 次，所以 $\sum\limits_{i=1}^n|s_i|=2k+n$

所以总时间复杂度 $\mathcal O(n+k)$

金组题比银组题增加了一个时间限制 $m$

记 $t=\lfloor \frac{m}{k}\rfloor$ 表示从一个点开始会完整走 $t$ 轮；$w=m-kt$ 表示走完 $t$ 轮还要走 $w$ 步

于是类似滑动窗口维护，每次暴力加入 $w$ 步，计算答案，再删除当前点，把加入 $w$ 步的节点剩下的都加进去

和银组题的复杂度分析一样，总复杂度 $\mathcal O(n+k)$

细节：注意 $t=0$ 的情况并且特判环大小 $\le t$ 的情况

code:

#include<bits/stdc++.h>
#define MAXN 200010
#define int long long
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define pii pair<int,int>
#define iter vector<pii>::iterator
using namespace std;
int n,K,m,vis[MAXN],ans[MAXN];
vector<pii>s[MAXN];
int cnt[MAXN],res;
int pos[MAXN],p[MAXN];
int q[MAXN],l,r;
void add(int x,int ti){
	for(iter it=s[x].begin();it!=s[x].end();it++){
		if(it->fi>ti)return;
		cnt[it->se]++;if(cnt[it->se]==1)res++;
	}
}
void del(int x,int ti){
	for(iter it=s[x].begin();it!=s[x].end();it++){
		if(it->fi>ti)return;
		cnt[it->se]--;if(!cnt[it->se])res--;
	}
}
signed main(){
	scanf("%lld%lld%lld",&n,&K,&m);
	for(int i=1;i<=n;i++)pos[i]=i,s[i].pb(mp(0,i));
	for(int i=1;i<=K;i++){
		int a,b;scanf("%lld%lld",&a,&b);
		s[pos[a]].pb(mp(i,b));s[pos[b]].pb(mp(i,a));
		swap(pos[a],pos[b]);
	}
	for(int i=1;i<=n;i++)p[pos[i]]=i;
	int t=m/K,w=m%K;
	for(int i=1;i<=n;i++){
		if(vis[i])continue;l=1,r=0;bool fl=0;
		for(int u=i,tim=1;tim<=t;u=p[u],tim++){
			if(u==i&&tim!=1){fl=1;break;}
			add(u,K);q[++r]=u;
		}
		if(fl){
			ans[i]=res;vis[i]=1;del(i,K);
			for(int u=p[i];u!=i;u=p[u])
				ans[u]=ans[i],del(u,K),vis[u]=1;
			continue;
		}p[0]=i;
		for(int u=i,tim=1;u!=i||tim==1;u=p[u],tim++){
			int nxt=p[q[r]];add(nxt,w);
			ans[u]=res;del(nxt,w);
			add(nxt,K);del(u,K);
			l++;q[++r]=nxt;vis[u]=1;
		}
		for(int j=l;j<=r;j++)del(q[j],K);
	}
	for(int i=1;i<=n;i++)printf("%lld\n",ans[i]);
	return 0;
}