#include <bits/stdc++.h>
using namespace std;
const int mx = 5e5 + 5;
int n, k, ans, indeg[mx], nxt[mx], dst[mx]; bool vis[mx];
void solveIndeg0(){
queue<int> q; memset(dst, 0x3f, sizeof(dst));
dst[1] = 0;
for (int i = 1; i <= n; i++) if (!indeg[i]) q.push(i);
while (!q.empty()){
int cur = q.front(), to = nxt[cur]; q.pop();
vis[cur] = 1;
if (dst[cur] > k) dst[cur] = 1, ans++;
dst[to] = min(dst[to], dst[cur] + 1);
if (!(--indeg[to])) q.push(to);
}
}
void solveCyc(int cur){
vector<int> nodes;
while (!vis[cur]) nodes.push_back(cur), vis[cur] = 1, cur = nxt[cur];
int sz = nodes.size(), jmp[sz], bst = 2e9; bool ok[sz] = {};
for (int i = 0, pos = i, D = 2e9; i < sz * 2; i++, pos = i % sz){
D = min(D + 1, dst[nodes[pos]]);
ok[pos] |= (D <= k);
}
for (int i = sz * 2 - 1, pos = i % sz, lst = 2e9; ~i; i--, pos = i % sz){
if (!ok[pos]) lst = pos;
jmp[pos] = lst - i;
}
for (int st = 0; st < min(sz, k); st++){
int trav = 0, tmp = 0;
while (1){
trav += jmp[(st + trav) % sz];
if (trav >= sz) break;
trav += k; tmp++;
}
bst = min(bst, tmp);
}
ans += bst;
}
int main(){
cin >> n >> k;
for (int i = 1; i <= n; i++){
int a, b; cin >> a >> b;
indeg[b]++; nxt[a] = b;
}
solveIndeg0();
for (int i = 1; i <= n; i++) if (!vis[i]) solveCyc(i);
cout<<ans<<endl;
}
