#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

const int mod = 1e9 + 7;

int add(int a, int b) {
    return a + b >= mod ? a + b : a + b - mod;
}
int sub(int a, int b) {
    return a - b < 0 ? a - b + mod : a - b;
}
int mult(int a, int b) {
    return a * 1ll * b % mod;
}
int bpow(int a, int b) {
    int ans = 1;
    while (b) {
        if (b & 1) ans = mult(ans, a);
        a = mult(a, a);
        b >>= 1;
    }
    return ans;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);

    int n, m, g;
    cin >> n >> m >> g;

    int cc = 0;
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;

        if (u != v) {
            cc++;
        }
    }

    if (g == 3) {
        cout << cc << "\n";
        cout << 1 << "\n";
    } else {
        return 0;
    }

    return 0;
}
