#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:10000000")
using namespace std;
template <typename T>
inline T abs(T a) {
  return ((a < 0) ? -a : a);
}
template <typename T>
inline T sqr(T a) {
  return a * a;
}
const int INF = (int)1E9 + 7;
const long double EPS = 1E-9;
const long double PI = 3.1415926535897932384626433832795;
const int NMAX = 2000000;
int n, m, k;
int c[NMAX];
int root(int v) { return c[v] == v ? v : c[v] = root(c[v]); }
bool merge(int a, int b) {
  a = root(a), b = root(b);
  if (a == b) return false;
  if (rand() & 1) swap(a, b);
  c[a] = b;
  return true;
}
int main() {
  srand(time(NULL));
  scanf("%d%d%d", &n, &m, &k);
  for (int v = 0; v < int(n); ++v) c[v] = v;
  for (int i = 0; i < int(m); ++i) {
    int a, b;
    scanf("%d%d", &a, &b);
    a--, b--;
    merge(a, b);
  }
  vector<int> comp(n, 0);
  for (int i = 0; i < int(n); ++i) comp[root(i)]++;
  long long sum = 0;
  multiset<int> q;
  for (int i = 0; i < int(n); ++i) {
    comp[i] = min(comp[i], k);
    if (comp[i] > 0) {
      sum += comp[i];
      q.insert(comp[i]);
    }
  }
  int ans = 0;
  while ((int((q).size()) - 1) * 2 > sum) {
    int a = *q.begin();
    q.erase(q.begin());
    int b = *q.begin();
    q.erase(q.begin());
    sum -= a + b;
    int c = min(a + b, k);
    sum += c;
    q.insert(c);
    ans++;
  }
  cout << ans << endl;
  return 0;
}
