// Created by rost on 08.03.25.

#include <bits/stdc++.h>

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

const int MAX_N = 2000;

int n, m;
vector<int> graph[MAX_N];

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

#ifdef LOCAL
    freopen("in.in", "r", stdin);
    freopen("out.out", "w", stdout);
#endif

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

        graph[v].push_back(u);
        graph[u].push_back(v);
    }

    int cnt = 0;
    for (int i = 0; i < n; ++i) {
        for (auto to: graph[i]) {
            if (to != i - 1 && to != i + 1) {
                ++cnt;
            }
        }
    }
    cout << (cnt/2) << '\n' << 1 << '\n';
}