#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> graph, rev;
vector<pair<int, int>> edges;
int n, m;
vector<int> way, used;

void dfs1(int v) {
    used[v] = true;
    for (auto elem : rev[v]) {
        if (!used[elem])
            dfs1(elem);
    }
    way.push_back(v);
}

int c = 1;
vector<int> color, col2;

void dfs2(int v) {
    color[v] = c;
    for (auto elem : graph[v]) {
        if (color[elem] == 0)
            dfs2(elem);
    }
}

vector<int> css(int mask) {
    graph.assign(n, {});
    rev.assign(n, {});
    for (int i = 0; i < m; i++) {
        if (mask >> i & 1) {
            graph[edges[i].second].push_back(edges[i].first);
            rev[edges[i].first].push_back(edges[i].second);
        } else {
            rev[edges[i].second].push_back(edges[i].first);
            graph[edges[i].first].push_back(edges[i].second);
        }
    }
    used.assign(n, 0);
    way.clear();
    for (int i = 0; i < n; i++) {
        if (!used[i]) dfs1(i);
    }
    reverse(way.begin(), way.end());
    color.assign(n, 0);
    c = 1;
    for (auto elem : way) {
        if (color[elem] == 0) {
            dfs2(elem);
            c++;
        }
    }
    col2.assign(n + 1, -1);
    for (int i = 0; i < n; i++) {
        if (col2[color[i]] == -1) {
            col2[color[i]] = i;
        }
        color[i] = col2[color[i]];
    }
    return color;
}

int main() {
    int g;
    cin >> n >> m >> g;
    edges.resize(m);
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        edges[i] = {--a, --b};
    }
    vector<int> need = css(0);
    vector<int> bad(1 << m);
    for (int mask = 1; mask < 1 << m; mask++) {
//        for (auto elem : css(mask)) cout << elem << ' ';
//        cout << '\n';
        bad[mask] = (css(mask) == need);
    }
    for (int j = 0; j < m; j++) {
        for (int mask = 0; mask < 1 << m; mask++) {
            if (mask >> j & 1) {
                bad[mask] |= bad[mask ^ (1 << j)];
            }
        }
    }
    int maxlen = 0, maxam = 0;
    for (int mask = 0; mask < 1 << m; mask++) {
        if (!bad[mask]) {
            int len = 0;
            for (int i = 0; i < m; i++) {
                len += mask >> i & 1;
            }
            if (maxlen == len) maxam++;
            if (maxlen < len) {
                maxam = 1;
                maxlen = len;
            }
        }
    }
    cout << maxlen << ' ' << maxam << '\n';
}
