#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 2;
const int inf = 1e9;
pair<int, int> edge[maxn];
int p[maxn];
int sz[maxn];
set<pair<int, int> > q;
int k;
int getId(int v) {
  if (p[v] == v) return v;
  return p[v] = getId(p[v]);
}
void merge(int v, int u) {
  sz[u] += sz[v];
  p[v] = u;
}
int f(int x) { return min(x, k); }
int main() {
  int n, m, v, u;
  int tunnel, cnt = 0;
  pair<int, int> a1, a2;
  scanf("%d%d%d", &n, &m, &k);
  for (int i = 0; i < m; i++) {
    scanf("%d%d", &edge[i].first, &edge[i].second);
    edge[i].first--;
    edge[i].second--;
  }
  for (int i = 0; i < n; i++) p[i] = i;
  for (int i = 0; i < n; i++) sz[i] = 1;
  cnt = n;
  for (int i = 0; i < m; i++) {
    v = getId(edge[i].first);
    u = getId(edge[i].second);
    if (v != u) {
      merge(v, u);
      cnt--;
    }
  }
  tunnel = 0;
  for (int i = 0; i < n; i++) {
    if (p[i] == i) {
      tunnel += f(sz[i]);
      q.insert(make_pair(sz[i], i));
    }
  }
  for (int i = 0;; i++) {
    if (tunnel / 2 >= cnt - 1) {
      cout << i << "\n";
      return 0;
    }
    a1 = *q.begin();
    q.erase(q.begin());
    a2 = *q.begin();
    q.erase(q.begin());
    tunnel -= f(a1.first);
    tunnel -= f(a2.first);
    tunnel += f(a1.first + a2.first);
    q.insert(make_pair(a1.first + a2.first, a1.second));
    cnt--;
  }
  return 0;
}
