#include <bits/stdc++.h>

using namespace std;

const int N = 2000 +123;

using ll = long long;

mt19937_64 rng (time (0));

#define int long long
int n, m, group;
vector<int> g[N];
bool used[N];
int ans = 0, cnt = 0, sz = 0;
void dfs (int v, int par = -1) {
    used[v] = 1;
    sz += 1;
    cnt += (int)g[v].size();
    for (auto to : g[v]) {
        if (!used[to]) dfs (to, v);
    }
}

void solve () {
    cin >> n >> m >> group;
    for (int i = 1; i <= m; ++i) {
        int u, v; cin >> u >> v;
        g[u].push_back (v);
        g[v].push_back (u);
    }
    cout << n - 1 << '\n';
    cout << "0\n";
    return;
    for (int i = 1; i <= n; ++i) if (!used[i]) {
        cnt = sz = 0;
        dfs (i);
        cnt /= 2;
        ans += (cnt - sz + 1);
    }
    if (group == 3 || group == 4) {
        cout << ans << '\n' << 0 << "\n";
    } else {
        assert(0);
    }
}

signed main() {
#ifdef local
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif // local
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int test = 1;
    while (test--) solve();
}
