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

using namespace std;

vector<vector<int>> gr, rg;
vector<int> used, ts;

void dfs(int v) {
    used[v] = 1;
    for (auto to : gr[v]) {
        if (used[to] != 1) {
            dfs(to);
        }
    }
    ts.push_back(v);
}

vector<int> c;

void nd(int v, int col) {
    c[v] = col;
    for (auto to : rg[v]) {
        if (c[to] == 0) {
            nd(to, col);
        }
    }
}

void make() {
    int n = gr.size();
    used.assign(n, 0);
    ts.clear();
    for (int i = 0; i < n; ++i) {
        if (!used[i]) {
            dfs(i);
        }
    }
    rg.assign(n, {});
    for (int i = 0; i < n; ++i) {
        for (auto to : gr[i]) {
            rg[to].push_back(i);
        }
    }
    reverse(ts.begin(), ts.end());
    c.assign(n, 0);
    int col = 1;
    for (int i = 0; i < n; ++i) {
        if (!c[ts[i]]) {
            nd(ts[i], col++);
        }
    }
    vector<int> f(n);
    int cl = 1;
    for (int i = 0; i < n; ++i) {
        if (!f[c[i]]) {
            f[c[i]] = cl++;
        }
        c[i] = f[c[i]];
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, m, g;
    cin >> n >> m >> g;
    gr.resize(n);
    vector<pair<int, int>> ed;
    int cnt = 1;
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        gr[u].push_back(v);
        cnt *= 3;
        ed.push_back({u, v});
    }
    make();
    vector<int> st = c;
    vector<bool> mm(1 << m, true);
    for (int i = 0; i < cnt; ++i) {
        if (i == 122) {
            int x;
            x++;
        }
        gr.assign(n, {});
        int mask = i;
        int m2 = 0;
        int ch = 0;
        for (int j = 0; j < m; ++j) {
            if (mask % 3 == 0) {
                gr[ed[j].first].push_back(ed[j].second);
            } else if (mask % 3 == 1) {
                m2 += (1 << j);
                gr[ed[j].first].push_back(ed[j].second);
            } else {
                m2 += (1 << j);
                gr[ed[j].second].push_back(ed[j].first);
                ch++;
            }
            mask /= 3;
        }
        make();
        if (c == st && ch) {
            mm[m2] = false;
        }
    }
    int a1 = 0, a2 = 0;
    for (int i = 0; i < (1 << m); ++i) {
        if (mm[i]) {
            int cc = 0;
            for (int j = 0; j < m; ++j) {
                if (i >> j & 1) {
                    cc++;
                }
            }
            if (cc > a1) {
                a1 = cc;
                a2 = 1;
            } else if (cc == a1) {
                a2++;
            }
        }
    }
    cout << a1 << ' ' << a2;
}
