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

using namespace std;

vector<vector<int>> gr;
vector<vector<int>> c;
vector<int> used;

void dfs(int v, int tm) {
    c[tm - 1][v] = 1;
    used[v] = tm;
    for (auto to : gr[v]) {
        if (used[to] != tm) {
            dfs(to, tm);
        }
    }
}

vector<vector<int>> k, ng;

void nd(int v) {
    k.back().push_back(v);
    used[v] = 1;
    for (auto to : ng[v]) {
        if (used[to] != 1) {
            nd(to);
        }
    }
}

void make() {
    int n = gr.size();
    used.assign(n, 0);
    c.assign(n, vector<int> (n));
    for (int i = 0; i < n; ++i) {
        dfs(i, i + 1);
    }
    ng.assign(n, {});
    k.clear();
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            if (c[i][j] && c[j][i]) {
                ng[i].push_back(j);
                ng[j].push_back(i);
            }
        }
    }
    used.assign(n, 0);
    for (int i = 0; i < n; ++i) {
        if (!used[i]) {
            k.push_back({});
            nd(i);
            sort(k.back().begin(), k.back().end());
        }
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, m, g;
    cin >> n >> m >> g;
    gr.resize(n);
    c.resize(n, vector<int> (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<vector<int>> st = k;
    vector<bool> mm(1 << m, true);
    for (int i = 0; i < cnt; ++i) {
        if (i == 273) {
            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 (m2 != 0 && k == 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;
}
