#include <bits/stdc++.h>
using namespace std;
long long pred[2000005];
long long last[2000005];
long long st[2000005], ed[2000005];
long long n, m, k;
bool vis[2000005];
queue<int> q;
long long k1 = 0, kn = 0, kc = 0;
void bfs(int x) {
  vis[x] = true;
  q.push(x);
  long long ans = 0;
  ans++;
  while (!q.empty()) {
    int a = q.front();
    q.pop();
    a = last[a];
    while (a > 0) {
      if (!vis[ed[a]]) {
        ans++;
        q.push(ed[a]);
        vis[ed[a]] = true;
      }
      a = pred[a];
    }
  }
  kc++;
  if (ans > k) ans = k;
  if (ans == 1)
    k1++;
  else
    kn += ans - 2;
}
int main() {
  scanf("%lld%lld%lld", &n, &m, &k);
  for (long long i = 1; i <= m; i++) {
    scanf("%lld%lld", &st[i], &ed[i]);
    st[i + m] = ed[i];
    ed[i + m] = st[i];
  }
  memset(last, 0, sizeof(last));
  for (long long i = 1; i <= 2 * m; i++) {
    pred[i] = last[st[i]];
    last[st[i]] = i;
  }
  memset(vis, 0, sizeof(vis));
  for (long long i = 1; i <= n; i++) {
    if (!vis[i]) bfs(i);
  }
  kn += 2;
  if (kc == 1)
    printf("%d", 0);
  else if (k == 1)
    printf("%d", kc - 2);
  else if (k1 <= kn)
    printf("%d", 0);
  else
    printf("%d", (k1 - kn + 1) / 2);
  return 0;
}
