#include <fstream>
#include <iostream>
#include <iomanip>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <queue>
#include <cmath>
#include <algorithm>
using namespace std;

using ll = long long;

//                                              ВАНЯ ПАНИН 542 ЛЕГЕНДА!!!!!

const int maxn = 2e3;
const int inf = 1e9 + 239;
const ll mod = 1e9 + 7;
vector<vector<int>> g(maxn, vector<int>(0));
vector<vector<int>> tg(maxn, vector<int>(0));
vector<int> tout(0);
vector<int> color(maxn, -1);
vector<ll> d(maxn, 0);
vector<int> p(maxn, 0);
vector<vector<pair<int, int>>> cyc(0);

vector<vector<int>> pp(maxn, vector<int>(maxn, -1));
vector<bool> in(0);

int cur = 0;

void dfs0(int v) {
  color[v] = 0;
  for (int u : g[v]) {
    if (color[u] == -1) {
      dfs0(u);
    }
  }
  tout.push_back(v);
}

void find_cycles(int v) {
  color[v] = cur;
  for (int u : g[v]) {
    if (color[u] == cur) {
      int w = v;
      int j = cyc.size();
      cyc.push_back({{v, u}});
      while (w != u) {
        cyc[j].push_back({p[w], w});
        w = p[w];
      }
    } else if (color[u] == 0) {
      find_cycles(u);
    }
  }
}

bool dfs(int j) {
  for (auto [u, v] : cyc[j]) {
    if (pp[u][v] == -1) {
      pp[u][v] = j;
      in[j] = true;
      return true;
    }
    if (pp[u][v] != j && in[pp[u][v]] && dfs(pp[u][v])) {
      in[j] = true;
      pp[u][v] = j;
      return true;
    }

  }
  return false;
}

void solve() {
  int n, m, gr;
  cin >> n >> m >> gr;
  for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    u--;
    v--;
    g[u].push_back(v);
    tg[v].push_back(u);
  }
  for (int i = 0; i < n; i++) {
    if (color[i] == -1) {
      dfs0(i);
    }
  }
  reverse(tout.begin(), tout.end());
  for (int v : tout) {
    if (color[v] == 0) {
      cur++;
      find_cycles(v);
    }
  }
  int k = cyc.size();
  in.assign(k, 0);
  bool flag = true;
  int ans = 0;
  while (flag) {
    flag = false;
    for (int i = 0; i < k; i++) {
      if (!in[i] && dfs(i)) {
        ans++;
        flag = true;
      }
    }
  }
  cout << m - ans << '\n' << rand() % mod;
}


//                                              ВАНЯ ПАНИН 542 ЛЕГЕНДА!!!!!


int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  solve();
}

//                                              ВАНЯ ПАНИН 542 ЛЕГЕНДА!!!!!

