#include <bits/stdc++.h>


using namespace std;


using ll = long long;


const ll mod = 1e9 + 7;


template<typename T>
ostream & operator <<(ostream &os, const vector<T> &a) {
    for (T el : a) {
        os << el << " ";
    }
    os << '\n';
    return os;
}


void dfs(const vector<vector<int>> &g, vector<bool> &used, int v, vector<int> &t) {
    used.at(v) = 1;
    for (int to : g.at(v)) {
        if (!used.at(to)) {
            dfs(g, used, to, t);
        }
    }
    t.push_back(v);
}


void jfs(const vector<vector<int>> &g, vector<int> &c, int v, int color) {
    c.at(v) = color;
    for (int to : g.at(v)) {
        if (c.at(to) == -1) {
            jfs(g, c, to, color);
        }
    }
}


void build(const vector<vector<int>> &g, const vector<vector<int>> &gt, int n, vector<vector<bool>> &comps) {
    vector<int> t;
    vector<bool> used(n, 0);
    for (int i = 0; i < n; i++) {
        if (!used.at(i)) {
            dfs(g, used, i, t);
        }
    }
    reverse(t.begin(), t.end());
    vector<int> c(n, -1);
    int color = 0;
    for (int i : t) {
        if (c.at(i) == -1) {
            jfs(gt, c, i, color);
            color++;
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (c.at(i) == c.at(j)) {
                comps.at(i).at(j) = 1;
            }
        }
    }
}


bool Check(int mask, const vector<pair<int, int>> &edges, int n, vector<vector<bool>> &comps) {
    vector<vector<int>> g(n), gt(n);
    for (int i = 0; i < int(edges.size()); i++) {
        int v = edges.at(i).first;
        int u = edges.at(i).second;
        int buf = ((1 << i) ^ mask);
        if (buf < mask) {
            swap(v, u);
        }
        g.at(v).push_back(u);
        gt.at(u).push_back(v);
    }
    vector<vector<bool>> new_comps(n, vector<bool>(n, 0));
    build(g, gt, n, new_comps);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (comps.at(i).at(j) != new_comps.at(i).at(j)) {
                return 0;
            }
        }
    }
    return 1;
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, group;
    cin >> n >> m >> group;
    vector<vector<int>> g(n), gt(n);
    vector<pair<int, int>> edges;
    for (int i = 0; i < m; i++) {
        int v, u;
        cin >> v >> u;
        v--;
        u--;
        g.at(v).push_back(u);
        gt.at(u).push_back(v);
        edges.push_back({v, u});
    }
    vector<vector<bool>> comps(n, vector<bool>(n, 0));
    build(g, gt, n, comps);
    int ans = 0, cnt = 0;
    vector<bool> prohibit((1 << m), 0);
    for (int mask = 0; mask < (1 << m); mask++) {
        prohibit.at(mask) = Check(mask, edges, n, comps);
        bool flag = 0;
        for (int sub = mask; sub > 0 && !flag; sub = (sub - 1) & mask) {
            flag = flag || prohibit.at(sub);
        }
        if (!flag) {
            int len = 0;
            for (int bit = 0; bit < m; bit++) {
                int buf = ((1 << bit) ^ mask);
                if (buf < mask) {
                    len++;
                }
            }
            if (len > ans) {
                ans = len;
                cnt = 1;
            } else if (len == ans) {
                cnt++;
            }
        }
    }
    cout << ans << '\n' << cnt;
    return 0;
}


/*2 2 0
1 2
2 1*/


/*5 6 0
1 2
1 5
2 3
3 4
3 5
4 2*/
