#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back

using namespace std;

typedef long long ll;
typedef long double ld;

const ll mod = 1e9+7;

ll bpow(ll a, ll n) {
    ll res = 1;
    while (n) {
        res *= a;
        if (n & 1) a *= a;
        n /= 2;
    }
    return res;
}

const int N = 5e5+52;
const int M = 2e3+52;

ll a[N];
int n, m;
ll  T;
ll pr[N], sf[N];
int p[N];
map<int,vector<int>> sp;

int main() {

    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
//return 0;
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    ll n,m,g;
    cin >> n >> m >> g;
    if (g == 3) {
        cout << m-n+1<<"\n";
        return 0;
    }
    vector<pair<int,int>> e;
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        p[u]++,p[v]++;
        e.pb({u,v});
    }
    int cnt = 0;
    for (auto it : e) {
        if (p[it.fi] > 1 && p[it.se] > 1) cnt++;
    }
    cout << cnt<< "\n";
    cout << "1\n";
    return 0;
}
