#include <bits/stdc++.h>
using namespace std;
const int maxn = 1000005;
int N, M, K;
int a[maxn], c[maxn];
int find(int v) {
  int tv = v;
  while (a[tv] != tv) tv = a[tv];
  while (v != tv) {
    int tmp = a[v];
    a[v] = tv;
    v = tmp;
  }
  return tv;
}
vector<int> vec;
int sum;
bool ok(int num) {
  int need = (vec.size() - num - 1) * 2;
  return sum >= need;
}
int solve() {
  if (vec.size() == 1) return 0;
  if (K == 1) return vec.size() - 1 - 1;
  int L = 0, R = (int)vec.size() - 1, ans = R;
  while (L <= R) {
    int mid = (L + R) / 2;
    if (ok(mid)) {
      ans = mid;
      R = mid - 1;
    } else
      L = mid + 1;
  }
  return ans;
}
int main() {
  while (scanf("%d%d%d", &N, &M, &K) != EOF) {
    for (int i = 1; i <= N; i++) {
      a[i] = i;
      c[i] = 1;
    }
    while (M--) {
      int t1, t2;
      scanf("%d%d", &t1, &t2);
      t1 = find(t1);
      t2 = find(t2);
      if (t1 == t2) continue;
      a[t1] = t2;
      c[t2] += c[t1];
    }
    vec.clear();
    sum = 0;
    for (int i = 1; i <= N; i++) {
      if (a[i] == i) {
        int tmp = min(c[i], K);
        vec.push_back(tmp);
        sum += tmp;
      }
    }
    printf("%d\n", solve());
  }
  return 0;
}
