#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const ll N = 2000 + 5;

vector<ll> g[N], gr[N];

vector<ll> order;

vector<pair<ll, ll>> e;

ll col[N], col_s[N];

ll used[N];
ll n, m, G;

void dfs1(ll v) {
    used[v] = 1;
    for(ll u: g[v]) {
        if (!used[u])dfs1(u);
    }
    order.push_back(v);
}

vector<ll> f;
void dfs2(ll v) {
    f.push_back(v);
    used[v] = 2;
    for(ll u: gr[v]) {
        if (used[u] != 2) {
            dfs2(u);
        }
    }
}

void flex() {
    for (int i = 0; i <= n; ++i) {
        g[i].clear();
        gr[i].clear();
        used[i] = 0;
    }
    order.clear();
    for (int i = 0; i < m; ++i) {
        auto [v, u] = e[i];
        g[v].push_back(u);
        gr[u].push_back(v);
    }
    for (int i = 1; i <= n; ++i) {
        if (!used[i]) {
            dfs1(i);
        }
    }
    std::reverse(order.begin(), order.end());
    for(ll u : order) {
        if (used[u] != 2) {
            f.clear();
            dfs2(u);
            std::sort(f.begin(), f.end());
            for(ll v : f) {
                col[v] = f[0];
            }
        }
    }
}

void solve() {
    cin >> n >> m >> G;
    for (int i = 0; i < m; ++i) {
        ll v, u;
        cin >> v >> u;
        e.emplace_back(v, u);
    }
    flex();
    swap(col, col_s);
    if (n <= 20) {
        ll mx = 0;
        ll cnt = 0;
        for (int i = 1; i <= (1 << m); ++i) {
            ll k = 0;
            vector<ll> pos;
            for (int j = 0; j < m; ++j) {
                if ((i >> j) & 1) {
                    k++;
                    pos.push_back(j);
                }
            }
            if (k < mx) {
                continue;
            }
            ll pk = 0;
            for (int j = 1; j <= (1 << k); ++j) {
                for (int l = 0; l < k; ++l) {
                    if ((j >> l) & 1) {
                        swap(e[pos[l]].first, e[pos[l]].second);
                    }
                }
                flex();
                ll pr = 0;
                for (int l = 0; l <= n; ++l) {
                    if (col[l] != col_s[l]) {
                        pr = 1;
                        break;
                    }
                }
                for (int l = 0; l < k; ++l) {
                    if ((j >> l) & 1) {
                        swap(e[pos[l]].first, e[pos[l]].second);
                    }
                }
                if (pr == 0) {
                    pk = 1;
                    break;
                }
            }
            if (pk == 0) {
                if (k > mx) {
                    mx = k;
                    cnt = 0;
                }
                cnt++;
            }
        }
        cout << mx << " " << cnt;
    } else {
        ll ans = 0;
        for (int i = 0; i < m; ++i) {
            swap(e[i].first, e[i].second);
            flex();
            ll pr = 0;
            for (int j = 0; j <= n; ++j) {
                if (col[j] != col_s[j]) {
                    pr = 1;
                    break;
                }
            }
            if (pr == 1) {
                ans++;
            }
            swap(e[i].first, e[i].second);
        }
        cout << ans << " " << 1;
    }
}

int main() {
    int test = 1;
    // cin >> test;
    while (test--) {
        solve();
    }
}



