给定一张N个点N条边的有向图，每个点出度为1。
求最少增加多少条有向边使得：从1到每个点的最短路径不大于K。
显然先要从出度为0的点开始将外面树上的所有点搞掉。
问题就转化为剩下一个环，并且环上有一些点已经染好色，可以将其中连续K个点染色，问将其全部染好的最小次数。
可以从某点开始染，预处理每个点隔K个之后下一个未染色的点。这样做一次是O(N/k)。
可以发现其实只要将任意连续K个未染色的点都做一次就保证能出最优解。总复杂度为O(K)*O(N/K)=O(N)。
算法其实不难，但尼玛细节搞死人啊！！！%>_<%
调了半天，最后还是靠std对拍才勉强搞到AC的。
树的预处理比较恶心，我开始算法也有bug。
环的细节还是不少的，写了各种版本，最后还是错了。
自己YY的东西还是想清楚，保证无误再写才好啊。
/*
Problem:
Algorithm:
Note:
*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<set>
#include<vector>
#include<map>
#include<string>
#include<iomanip>
#include<iostream>
#include<cmath>
#include<queue>
using namespace std;
#define rep(i,x,y) for(i=x;i<=y;i++)
#define _rep(i,x,y) for(i=x;i>=y;i--)
#define CL(S,x) memset(S,x,sizeof(S))
#define CP(S1,S2) memcpy(S1,S2,sizeof(S2))
#define ALL(x,S) for(x=S.begin();x!=S.end();x++)
#define sqr(x) ((x)*(x))
#define mp make_pair
#define fi first
#define se second
#define upmin(x,y) x=min(x,y)
#define upmax(x,y) x=max(x,y)
typedef long long ll;
typedef long double ld;
void read(int&x){bool fu=0;char c;for(c=getchar();c<=32;c=getchar());if(c=='-')fu=1,c=getchar();for(x=0;c>32;c=getchar())x=x*10+c-'0';if(fu)x=-x;};
char getc(){char c;for(c=getchar();c<=32;c=getchar());return c;}
const int N=500010;
const int inf=1000000000;
int n,K,i,j,p,x,y,z,w,g,huan,have,totl,start,it;
int cs[N],dis[N],d[N],next[N],path[N],ans,q[N],xia[N],go[N],cnt,l[N],qian[N];
bool v[N],cir[N],need[N];int ti[N];
void markcir()
{
rep(p,1,n)if(!v[p])
{
i=p;while(!v[i]){ti[i]=p;v[i]=1;i=next[i];}
if(ti[i]!=p)continue;
huan++;cs[huan]=i;
start=i;do{cir[i]=1;i=next[i];}while(i!=start);
}
}
void bfs()
{
CL(dis,127);
j=0;rep(i,2,n)if(d[i]==0)q[++j]=i,dis[i]=1,ans++;
if(d[1]==0)q[++j]=1,dis[1]=0;
if(cir[1])q[++j]=1,dis[1]=0;
for(i=1;i<=j;i++)
{
p=next[q[i]];w=dis[q[i]]+1;
if(cir[p])
{
if(w<=K&&w<dis[p])
{
dis[p]=w;q[++j]=p;
}
}
else
{
upmin(dis[p],w);
if(--d[p]==0)
{
if(p==1)dis[p]=0;
else if(dis[p]>K){dis[p]=1,ans++;}
q[++j]=p;
}
}
}
rep(i,1,n)if(cir[i]&&dis[i]==dis[0])need[i]=1,have++;
}
int u;
bool pdin(int i,int l,int r)
{
if(l<=r)return i>=l&&i<=r;
return i<=r||i>=l;
}
int solvecir(int start)
{
i=start;g=have=0;
do{path[++g]=i;if(need[i])have++;i=next[i];}while(i!=start);
if(have<=1)return have;
if(g<=K)return 1;
rep(i,1,g)if(need[path[i]])break;start=i;
xia[start]=start;p=start;
for(i=(start+g-2)%g+1;i!=start;i=(i+g-2)%g+1){if(need[path[i]])p=i;xia[i]=p;}
int best=inf;
i=start;cnt=0;
while(1)
{
j=i;
int res=0;
while(1)
{
res++;
u=xia[(j+K-1)%g+1];
if(pdin(i,j+1,u))break;
j=u;
}
upmin(best,res);
i=xia[i%g+1];++cnt;if(cnt>K)break;
}
return best;
}
int main()
{
freopen("B.in","r",stdin);
freopen("B.out","w",stdout);
read(n);read(K);rep(i,1,n)read(x),read(y),next[x]=y,d[y]++;
markcir();
bfs();
rep(it,1,huan)
ans+=solvecir(cs[it]);
printf("%d
",ans);
scanf("
");
return 0;
}