显然在最优解中，添加的边都是从$1$出发的。
这个图是一个环套树的结构，对于树的部分，显然叶子节点必须加边。
因此可以自底向上确定树中哪些节点需要加边，同时得到$1$到环上每个点的距离。
对于每个环，首先求出哪些点距离超过了$k$，并预处理出每个点之后最近的未满足的点的位置。
然后枚举起点，显然起点必须未满足，然后向右$k$步$k$步跳，贪心覆盖，对于长度为$L$的环，每次求答案的时间复杂度为$O(\frac{L}{k})$。
注意到每个环中每$k$个起点中必然存在一个最优解，因此只需要枚举$k$个起点，时间复杂度为$O(\frac{L}{k}\times k)=O(L)$。
时间复杂度$O(n)$。
#include<cstdio>
const int N=500010,M=N*2;
int n,m,i,j,k,x,y,d[N],out[N],v[N],g[N],nxt[N],vis[N],on[N],f[N],ans;
int q[N],cnt,s[M],ok[M],go[M],now,ret,have;
inline void read(int&a){char c;while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';}
void dfs(int x){
vis[x]=1;
if(!d[x]){
f[x]=x==1?0:1;
if(x>1)ans++;
return;
}
f[x]=N;
for(int i=g[x];i;i=nxt[i]){
int y=v[i];
if(on[y])continue;
dfs(y);
if(f[x]>f[y])f[x]=f[y];
}
f[x]++;
if(x==1)f[x]=0;
if(!on[x]&&f[x]>m)f[x]=1,ans++;
}
int main(){
read(n),read(m);
for(i=1;i<=n;i++){
read(x),read(y);
out[x]=y;v[i]=x;nxt[i]=g[y];g[y]=i;
d[y]++;
}
for(i=1;i<=n;i++)if(!vis[i]){
for(j=i;!vis[j];j=out[j])vis[j]=1;
on[q[cnt=1]=j]=1;
for(k=out[j];k!=j;k=out[k])on[k]=1,q[++cnt]=k;
for(j=1;j<=cnt;j++)dfs(q[j]),s[j]=s[j+cnt]=0;
for(j=1;j<=cnt;j++)if(f[q[j]]<=m){
s[j]++;
if(j+m-f[q[j]]<cnt+cnt)s[j+m-f[q[j]]+1]--;
}
for(j=1;j<=cnt+cnt;j++)s[j]+=s[j-1];
for(j=1;j<=cnt;j++)if(s[j]||s[j+cnt])ok[j]=ok[j+cnt]=1;else ok[j]=ok[j+cnt]=0;
go[cnt+cnt+1]=cnt+cnt+1;
for(j=cnt+cnt;j;j--)if(ok[j])go[j]=go[j+1];else go[j]=j;
have=0,now=N;
for(j=1;j<=cnt;j++)if(!ok[j]){
for(ret=0,k=j;k<j+cnt;){
ret++,k+=m;
if(k<j+cnt)k=go[k];
}
if(ret<now)now=ret;
if((++have)==m)break;
}
if(now<N)ans+=now;
}
return printf("%d",ans),0;
}