AC

#include <iostream>
#include <vector>
#include <bitset>
#include <cmath>
#include <algorithm>

using namespace std; const int MAXN = 20005; int parent[MAXN]; int sizeComp[MAXN]; int find(int x) {

if (parent[x] != x) {
    parent[x] = find(parent[x]);
}
return parent[x];

} void unionSets(int a, int b) {

a = find(a);
b = find(b);
if (a != b) {
    if (sizeComp[a] < sizeComp[b]) {
        swap(a, b);
    }
    parent[b] = a;
    sizeComp[a] += sizeComp[b];
}

} int main() {

int n, k, m;
cin >> n >> k >> m;
for (int i = 1; i <= n; i++) {
    parent[i] = i;
    sizeComp[i] = 1;
}
for (int i = 0; i < k; i++) {
    int a, b;
    cin >> a >> b;
    unionSets(a, b);
}
vector<int> groups;
for (int i = 1; i <= n; i++) {
    if (parent[i] == i) {
        groups.push_back(sizeComp[i]);
    }
}
bitset<MAXN> dp;
dp[0] = 1;
for (int s : groups) {
    dp |= (dp << s);
}
int best = 0;
int minDiff = n;
for (int i = 0; i <= n; i++) {
    if (dp[i]) {
        int diff = abs(i - m);
        if (diff < minDiff) {
            minDiff = diff;
            best = i;
        } else if (diff == minDiff) {
            if (i < best) {
                best = i;
            }
        }
    }
}
cout << best << endl;
return 0;

}