#include <bits/stdc++.h>

using namespace std;
#define int long long

const int N = 2010;

vector<int> g[N], bigG[N];
int comp[N], cur = 1;

vector<vector<int>> ord;

bool good[N][N];

void dfs(int st, int v) {
    good[st][v] = true;
    for (auto u: g[v])
        if (!good[st][u])
            dfs(st, u);
}

void gfs(int v, int cnt) {
    comp[v] = cnt;
    ord[cnt].emplace_back(v);
    for (auto u: bigG[v]) {
        if (comp[u] == 0)
            gfs(u, cnt);
    }
}

int solve(vector<pair<int, int>> edges, int n) {
    int m = (int) edges.size(), cnt = 0;
    for (int ii = 0; ii < m; ii++) {
        vector<int> gr[n];
        for (int j = 0; j < m; j++) {
            if (ii != j)
                gr[edges[j].first].emplace_back(edges[j].second);
            else
                gr[edges[j].second].emplace_back(edges[j].first);
        }
        int col[n], gd = 0;
        for (int i = 0; i < n; i++) col[i] = 0;
        function<void(int)> dfs = [&](int v) {
            col[v] = 1;
            for (auto u: gr[v]) {
                if (col[u] == 1)
                    gd = 1;
                if (col[u] == 0)
                    dfs(u);
            }
            col[v] = 2;
        };
        for (int i = 0; i < n; i++) {
            if (col[i] == 0)
                dfs(i);
        }
        if (gd) cnt++;
    }
    return cnt;
}

bool exist(vector<pair<int, int>> &edges, vector<int> ver, int n) {
    vector<int> gr[n], col(n, 0);
    for (auto [u, v]: edges) gr[u].emplace_back(v);
    function<void(int)> dfs = [&](int v) {
        col[v] = 1;
        for (auto u: gr[v]) {
            if (col[u] == 0)
                dfs(u);
        }
    };
    for (int i: ver) {
        fill(col.begin(), col.end(), 0);
        dfs(i);
        for (int j: ver) {
            if (col[j] == 0)
                return false;
        }
    }
    return true;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    ord.emplace_back();
    int n, m, G;
    cin >> n >> m >> G;
    int u[m], v[m];
    for (int i = 0; i < m; i++) {
        cin >> u[i] >> v[i];
        u[i]--, v[i]--;
    }
    for (int i = 0; i < n; i++) {
        dfs(i, i);
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i != j && good[i][j] && good[j][i]) {
                bigG[i].emplace_back(j);
                bigG[j].emplace_back(i);
            }
        }
    }
    vector<pair<int, int>> e;
    for (int i = 0; i < n; i++) {
        if (comp[i] == 0) {
            ord.emplace_back();
            gfs(i, cur++);
        }
    }
    int ans = 0;
    for (int i = 0; i < m; i++) {
        if (comp[u[i]] != comp[v[i]]) {
            e.emplace_back(comp[u[i]] - 1, comp[v[i]] - 1);
        }
    }
    ans += solve(e, cur - 1);
    for (int i = 1; i < cur; i++) {
        vector<pair<int, int>> edges;
        for (int j = 0; j < m; j++) {
            if (comp[u[j]] == comp[v[j]] && comp[u[j]] == i) {
                edges.emplace_back(u[j], v[j]);
            }
        }
        vector<int> ver;
        for (int j = 0; j < n; j++) if (comp[j] == i) ver.emplace_back(j);
        for (int j = 0; j < (int) edges.size(); j++) {
            swap(edges[j].first, edges[j].second);
            if (!exist(edges, ver, n))
                ans++;
            swap(edges[j].first, edges[j].second);
        }
    }
    cout << ans - 1 << "\n" << 1;
    return 0;
}