#include <bits/stdc++.h>
using namespace std;
int mark[1000010];
vector<int> l[1000010];
vector<int> sizes;
void fin(int x) {
  cout << x << endl;
  exit(0);
}
struct province {
  int freeVertices;
  int freeConnections;
  bool operator<(const province &ot) const {
    return freeVertices < ot.freeVertices;
  }
};
int main() {
  int n, m, k;
  cin >> n >> m >> k;
  for (int i = 0; i < m; i++) {
    int a, b;
    cin >> a >> b;
    l[a].push_back(b);
    l[b].push_back(a);
  }
  int curMark = 1;
  for (int i = 1; i <= n; i++) {
    if (mark[i] == 0) {
      queue<int> q;
      q.push(i);
      mark[i] = curMark;
      int curSize = 0;
      while (!q.empty()) {
        int cur = q.front();
        ++curSize;
        q.pop();
        for (int u = 0; u < l[cur].size(); u++) {
          if (mark[l[cur][u]] == 0) {
            mark[l[cur][u]] = curMark;
            q.push(l[cur][u]);
          }
        }
      }
      ++curMark;
      sizes.push_back(curSize);
    }
  }
  if (sizes.size() <= 2) fin(0);
  if (k == 1) fin(sizes.size() - 2);
  deque<province> all;
  for (int i = 0; i < sizes.size(); i++) {
    province p;
    p.freeConnections = k;
    p.freeVertices = sizes[i];
    all.push_back(p);
  }
  sort(all.begin(), all.end());
  reverse(all.begin(), all.end());
  deque<province> toConnect;
  toConnect.push_back(all[0]);
  all.pop_front();
  int sum = 0;
  int one = 0;
  for (; all.size();) {
    while (toConnect.size() && (toConnect[0].freeConnections == 0 &&
                                toConnect[0].freeVertices == 0))
      toConnect.pop_front();
    if (toConnect.size() && toConnect[0].freeConnections == 1 ||
        toConnect[0].freeVertices == 1) {
      if (all[0].freeVertices == 1) {
        int xxx = 0;
        sum += (all.size() + xxx) / 2;
        break;
      }
      toConnect[0] = all[0];
      toConnect[0].freeConnections--;
      toConnect[0].freeVertices--;
      all.pop_front();
      continue;
    }
    province last = *all.rbegin();
    all.pop_back();
    toConnect[0].freeConnections--;
    toConnect[0].freeVertices--;
    last.freeConnections--;
    last.freeVertices--;
    toConnect.push_back(last);
    if (last.freeVertices == 0) ++one;
  }
  cout << sum << endl;
  return 0;
}
