#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <cstdint>
using namespace std;
#define int long long

void solution();

int32_t main() {
#ifdef LOCAL
    freopen("test", "r", stdin);
    freopen("out", "w", stdout);
#endif

    int t = 1;
    // cin >> t;
    while (t--) {
        solution();
    }
}

vector<vector<int>> gr;
vector<vector<int>> gr1;
vector<int> ts;
vector<bool> used;

void calc_ts(int s) {
    used[s] = true;
    for (auto v : gr[s]) {
        if (used[v]) continue;
        calc_ts(v);
    }
    ts.push_back(s);
}

vector<int> col;

void dfs(int s, int cur) {
    col[s] = cur;
    for (auto v : gr1[s]) {
        if (col[v] != -1) continue;
        dfs(v, cur);
    }
}

void solution() {
    int n, m, g;
    cin >> n >> m >> g;

    gr.resize(n);
    gr1.resize(n);
    vector<pair<int, int>> edges;
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        u--; v--;

        edges.emplace_back(u, v);
        gr[u].push_back(v);
        gr1[v].push_back(u);
    }

    used.resize(n);
    for (int i = 0; i < n; ++i) {
        if (!used[i]) calc_ts(i);
    }
    reverse(ts.begin(), ts.end());

    col.assign(n, -1);
    int cur = 0;
    for (int i = 0; i < n; ++i) {
        if (col[i] != -1) continue;
        dfs(i, cur++);
    }

    vector<int> col_mx(cur);
    for (int i = 0; i < n; ++i) {
        col_mx[col[i]] = max(col_mx[col[i]], i);
    }

    vector<int> orig(n);
    for (int i = 0; i < n; ++i) {
        orig[i] = col_mx[col[i]];
    }

    vector<bool> change(1 << m);
    for (int mask = 1; mask < 1 << m; ++mask) {
        for (int i = 0; i < m; ++i) {
            if (mask >> i & 1) {
                if (change[mask ^ (1 << i)]) {
                    change[mask] = true;
                    break;
                }
            }
        }
        if (change[mask]) continue;
        
        gr.assign(n, vector<int>());
        gr1.assign(n, vector<int>());
        for (int i = 0; i < m; ++i) {
            auto [u, v] = edges[i];
            if (mask >> i & 1) {
                gr[v].push_back(u);
                gr1[u].push_back(v);
            } else {
                gr[u].push_back(v);
                gr1[v].push_back(u);
            }
        }
            
        used.assign(n, false);
        ts.clear();
        for (int i = 0; i < n; ++i) {
            if (!used[i]) calc_ts(i);
        }
        reverse(ts.begin(), ts.end());

        col.assign(n, -1);
        int cur = 0;
        for (auto i : ts) {
            if (col[i] != -1) continue;
            dfs(i, cur++);
        }

        vector<int> col_mx(cur);
        for (int i = 0; i < n; ++i) {
            col_mx[col[i]] = max(col_mx[col[i]], i);
        }

        vector<int> copy(n);
        for (int i = 0; i < n; ++i) {
            copy[i] = col_mx[col[i]];
        }

        bool flag = true;
        for (int i = 0; i < n; ++i) {
            if (copy[i] != orig[i]) {
                flag = false;
                break;
            }
        }
        change[mask] = flag;
    }

    pair<int, int> mx = {0, 1};
    for (int mask = 1; mask < 1 << m; ++mask) {
        int sz = 0;
        if (change[mask]) continue;
        for (int i = 0; i < m; ++i) {
            if (mask >> i & 1) sz++;
        }
        if (sz > mx.first) mx = {sz, 1};
        else if (sz == mx.first) mx.second++;
    }

    cout << mx.first << '\n' << mx.second << '\n';
}