#include <bits/stdc++.h>

#ifndef LOCAL
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#endif

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

using namespace std;
using ll = long long;

const int mod = 1e9 + 7;

struct Modular {
    int x;

    Modular(int x = 0): x(x) {}

    friend Modular operator+(Modular a, Modular b) {
        int res = a.x + b.x;
        return res - (res >= mod ? mod : 0);
    }

    friend Modular operator-(Modular a, Modular b) {
        int res = a.x - b.x;
        return res + (res < 0 ? mod : 0);
    }

    friend Modular operator*(Modular a, Modular b) {
        return ll(a.x) * b.x % mod;
    }
};


const int maxn = 2000;
set<int> g[maxn];
set<int> rg[maxn];
int usd[maxn];
int ct[maxn];

bool dfs1(int v) {
    usd[v] = 1;
    for(int i: g[v]) {
        if (usd[i] == 1 || (!usd[i] && dfs1(i))) {
            return true;
        }
    }
    usd[v] = 2;
    return false;
}

bool dfs2(int v) {
    usd[v] = 1;
    for(int i: rg[v]) {
        if (usd[i] == 1 || (!usd[i] && dfs2(i))) {
            return true;
        }
    }
    usd[v] = 2;
    return false;
}

void solve() {
    int n, m, e;
    cin >> n >> m >> e;
    vector<pair<int, int>> eds;
    vector<bool> vec(m);
    for(int i = 0; i < m; ++i){
        int a, b;
        cin >> a >> b;
        --a, --b;
        g[a].insert(b);
        ++ct[b];
        eds.emplace_back(a, b);
    }
    int cnt = 0;
    Modular ans = 1;
    for(int i = 0; i < m; ++i) {
        auto [a, b] = eds[i];
        g[a].erase(b);
        rg[b].erase(a);
        memset(usd, 0, sizeof usd);
        dfs1(0);
        bool f = true;
        for (int i = 0; i < n; ++i) {
            if(usd[i] == false) {
                f = false;
            }
        }
        memset(usd, 0, sizeof usd);
        dfs2(0);
        for (int i = 0; i < n; ++i) {
            if (usd[i] == false) {
                f = false;
            }
        }
        if (!f) {
            g[a].insert(b);
            g[b].insert(a);
            vec[i] = true;
        } else {
            ++cnt;
        }
    }
    cout << m - cnt - 1 << "\n" << m - cnt;
}

signed main() {
#ifndef LOCAL
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
#else
    freopen("C:\\Users\\User\\aboab\\input.txt", "r", stdin);
#endif
    solve();
}