#include <iostream>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <set>
#include <bitset>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <cmath>
#include <iomanip>
#include <algorithm>
#include <random>

using namespace std;

random_device rd;
mt19937 rnd(rd());

// #define int long long
using pii = pair<int, int>;

const int max_n = 21, inf = 1e9 + 57;

vector<int> g[max_n], t[max_n];
vector<bool> used(max_n, false);
vector<int> c(max_n, -1);
vector<int> ord;
int cnt = 0;

void dfs1(int v) {
    used[v] = true;
    for (int u : g[v]) {
        if (!used[u]) {
            dfs1(u);
        }
    }
    ord.push_back(v);
}

void dfs2(int v) {
    c[v] = cnt;
    for (int u : t[v]) {
        if (c[u] == -1) {
            dfs2(u);
        }
    }
}

vector<int> calc_css(int n, vector<pii> ve, int mask) {
    ord = {};
    cnt = 0;
    for (int i = 0; i < n; i++) {
        c[i] = -1;
        used[i] = false;
        g[i] = {};
        t[i] = {};
    }
    int m = ve.size();
    for (int i = 0; i < m; i++) {
        if ((mask >> i) & 1) {
            g[ve[i].second].push_back(ve[i].first);
            t[ve[i].first].push_back(ve[i].second);
        } else {
            g[ve[i].first].push_back(ve[i].second);
            t[ve[i].second].push_back(ve[i].first);
        }
    }
    for (int i = 0; i < n; i++) {
        if (!used[i]) {
            dfs1(i);
        }
    }
    reverse(ord.begin(), ord.end());
    for (int i : ord) {
        if (c[i] == -1) {
            dfs2(i);
            cnt++;
        }
    }
    vector<int> mn(cnt, inf);
    for (int i = 0; i < n; i++) {
        mn[c[i]] = min(mn[c[i]], i);
    }
    vector<int> res(n);
    for (int i = 0; i < n; i++) {
        res[i] = mn[c[i]];
    }
    return res;
}

struct snm {
    vector<int> p;
    snm(int n) {
        p.resize(n);
        for (int i = 0; i < n; i++) {
            p[i] = i;
        }
    }
    int get(int x) {
        if (x == p[x]) {
            return x;
        }
        return p[x] = get(p[x]);
    }
    void unite(int a, int b) {
        a = get(a);
        b = get(b);
        if (a == b) {
            return;
        }
        p[a] = b;
    }
};

bool comp(pii l, pii r) {
    return l.second - l.first < r.second - r.first;
}

void solve() {
    int n, m, gr; cin >> n >> m >> gr;
    vector<pii> ve;
    for (int i = 0; i < m; i++) {
        int v, u; cin >> v >> u;
        v--, u--;
        ve.emplace_back(v, u);
    }
    snm s(n);
    sort(ve.begin(), ve.end(), comp);
    std::reverse(ve.begin(), ve.end());
    int res = 0;
    for (auto [v, u] : ve) {
        if (s.get(v) == s.get(u)) {
            res++;
        }
        s.unite(v, u);
    }
    cout << res << endl;
    cout << 1 << endl;







































}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
}
