#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <algorithm>

using namespace std;

typedef long long ll;
typedef long double ld;

const ll inf = 1e18;
const ll mod = 1e9 + 7;

ll n, m, gg;
vector<vector<ll>> g1;
vector<vector<ll>> g2;
vector<vector<ll>> g;
vector<ll> was;
vector<ll> c;
vector<ll> res;
vector<ll> n1;
ll col = 0;

void dfs1(ll v) {
    was[v] = 1;
    for(ll to : g1[v]) {
        if (was[to] == 0) {
            dfs1(to);
        }
    }
    res.push_back(v);
}

vector<ll> p;
vector<ll> sz;

ll get(ll v) {
    if (p[v] == v) return v;
    return p[v] = get(p[v]);
}

ll merge(ll a, ll b) {
    ll a1 = get(a), b1 = get(b);
    if (sz[a1] < sz[b1]) swap(a1, b1);
    if (a1 != b1) {
        p[b1] = a1;
        sz[a1] += sz[b1];
        return 1;
    }
    return 0;
}

void dfs2(ll v, ll c1) {
    was[v] = 1;
    c[v] = c1;
    for(ll to : g2[v]) {
        if (was[to] == 0) {
            dfs2(to, c1);
        }
    }
}

void solve() {
    cin >> n >> m >> gg;
    g.assign(n, {});
    g1.assign(n, {});
    g2.assign(n, {});
    was.assign(n, 0);
    c.assign(n, 0);
    p.assign(n, 0);
    sz.assign(n, 1);
    n1.assign(n, 0);
    for(int i = 0; i < n; i++) p[i] = i;
    vector<pair<ll, ll>> z(m);
    for(int i = 0; i < m; i++) {
        ll a, b; cin >> a >> b;
        a--; b--;
        g1[a].push_back(b);
        g2[b].push_back(a);
        g[a].push_back(b);
        g[b].push_back(a);
        z[i] = {a, b};
        col += merge(a, b);
    }
    for(int i = 0; i < n; i++) {
        if (was[i] == 0) {
            dfs1(i);
        }
    }
    reverse(res.begin(), res.end());
    fill(was.begin(), was.end(), 0);
    res.clear();
    ll c1 = 1;
    for(int i = 0; i < n; i++) {
        ll v = res[i];
        if (was[v] == 0) {
            dfs2(v, c1);
            c1++;
        }
    }
    vector<ll> c_need = c;
    ll ans = 0, cl = 0, iter = 0;
    for(int i = 0; i < (1 << m); i++) {
        ll col1 = 0;
        for(int j = 0; j < (1 << m); j++) {
            if ((i & j) != 0) continue;
            g.assign(n, {});
            g1.assign(n, {});
            g2.assign(n, {});
            was.assign(n, 0);
            c.assign(n, 0);
            for(int j1 = 0; j1 < m; j1++) {
                if ((i & (1 << j1)) == 0) continue;
                ll a = z[j1].first, b = z[j1].second;
                g1[a].push_back(b);
                g2[b].push_back(a);
            }
            for(int j1 = 0; j1 < m; j1++) {
                ll a = z[j1].first, b = z[j1].second;
                if ((j & (1 << j1)) == 0) {
                    g1[a].push_back(b);
                    g2[b].push_back(a);
                } else {
                    swap(a, b);
                    g1[a].push_back(b);
                    g2[b].push_back(a);
                }
            }
            res.clear();
            fill(was.begin(), was.end(), 0);
            for(int i1 = 0; i1 < n; i1++) {
                if (was[i1] == 0) {
                    dfs1(i1);
                }
            }
            reverse(res.begin(), res.end());
            fill(was.begin(), was.end(), 0);
            res.clear();
            c1 = 1;
            for(int i1 = 0; i1 < n; i1++) {
                ll v = res[i1];
                if (was[v] == 0) {
                    dfs2(v, c1);
                    c1++;
                }
            }
            ll ok = 1;
            for(int j1 = 0; j1 < n; j1++) {
                for(int j2 = 0; j2 < n; j2++) {
                    iter++;
                    if (c_need[j1] == c_need[j2] && c[j1] != c[j2]) ok = 0;
                    if (c_need[j1] != c_need[j2] && c[j1] == c[j2]) ok = 0;
                }
            }
            if (iter >= ll(5 * 1e7)) break;
            if (ok) col1++;
            if (col1 > 1) break;
        }
        if (col1 == 1) {
            if (ans == m - (__builtin_popcount(i))) {
                ans = m - (__builtin_popcount(i));
                cl++;
            } else if (ans < m - (__builtin_popcount(i))) {
                ans = m - (__builtin_popcount(i));
                cl = 1;
            }
        }
        if (iter >= ll(5 * 1e7)) break;
    }
    cout << ans << " " << cl << "\n";
}

int main() {
#ifdef KABANDJAN
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll ttt = 1;
//    cin >> ttt;
    while(ttt--) {
        solve();
    }
    return 0;
}
