#include <bits/stdc++.h>

using ll = long long;
using ld = long double;
using namespace std;

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

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

    vector<vector<int>> graph(n);
    for(int i = 0; i < m; ++i){
        int u, v;
        cin >> u >> v;
        --u;
        --v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    if(g == 3){
        cout << m - (n - 1) << endl << 1;
    } else if(g == 4){
        cout << 0 << endl << -1;
    }
}
