#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>

using namespace std;

// #define int long long
using ld = long double;
using ll = long long;
using pii = pair<int, int>;

vector<int> find_components(const vector<vector<int>> &g)
{
    int n = g.size();
    vector<vector<int>> rg(n);
    for (int a = 0; a < n; ++a)
    {
        for (const auto &b : g[a])
        {
            rg[b].push_back(a);
        }
    }

    vector<bool> used(n, false);

    vector<int> arr;
    arr.reserve(n);
    function<void(int)> dfs = [&](int v)
    {
        used[v] = true;
        for (const auto &u : g[v])
        {
            if (used[u])
                continue;
            dfs(u);
        }
        arr.push_back(v);
    };
    for (int i = 0; i < n; ++i)
    {
        if (used[i])
            continue;
        dfs(i);
    }
    reverse(arr.begin(), arr.end());
    vector<int> comp(n, -1);
    function<void(int, int)> dfs2 = [&](int v, int c)
    {
        comp[v] = c;
        for (const auto &u : rg[v])
        {
            if (comp[u] != -1)
            {
                continue;
            }
            dfs2(u, c);
        }
    };
    int nxt = 0;
    for (const auto &v : arr)
    {
        if (comp[v] != -1)
        {
            continue;
        }
        dfs2(v, nxt);
        ++nxt;
    }

    return comp;
}

bool eq1(const vector<int> &a, const vector<int> &b)
{
    const int n = a.size();
    vector<int> r(n, -1);
    for (int i = 0; i < n; ++i)
    {
        if (r[a[i]] == -1)
        {
            r[a[i]] = b[i];
        }
        if (r[a[i]] != b[i])
        {
            return false;
        }
    }
    return true;
}

bool eq(const vector<int> &a, const vector<int> &b)
{
    return eq1(a, b) && eq1(b, a);
}

struct Edge
{
    int a, b;
};

void solve()
{
    int n, m, G;
    cin >> n >> m >> G;
    vector<Edge> ed(m);
    vector<vector<int>> sg(n);
    for (int i = 0; i < m; ++i)
    {
        cin >> ed[i].a >> ed[i].b;
        --ed[i].a;
        --ed[i].b;
        sg[ed[i].a].push_back(ed[i].b);
    }

    auto sc = find_components(sg);

    vector<bool> bad((1 << m), false);
    vector<bool> used((1 << m), false);

    int ans = 0;
    int ans_cnt = 1;

    int needed = (1 << 0) + (1 << 1) + (1 << 4);
    for (int mask = 1; mask < (1 << m); ++mask)
    {
        int sz = 0;
        vector<vector<int>> g(n);
        for (int i = 0; i < m; ++i)
        {
            if (mask & (1 << i))
            {
                g[ed[i].b].push_back(ed[i].a);
                ++sz;
                int u = mask - (1 << i);
                bad[mask] = bad[mask] || bad[u];
            }
            else
            {
                g[ed[i].a].push_back(ed[i].b);
            }
        }
        if (bad[mask])
            continue;
        auto c = find_components(g);
        if (eq(sc, c))
        {
            bad[mask] = true;
        }
        if (bad[mask])
            continue;

        if (sz > ans)
        {
            ans = sz;
            ans_cnt = 1;
        }
        else if (sz == ans)
        {
            ++ans_cnt;
        }
    }

    cout << ans << '\n';
    cout << ans_cnt << '\n';
}

signed main()
{
#ifdef ROMALOCAL
    freopen("in.txt", "r", stdin);
#endif

    cin.tie(0);
    ios::sync_with_stdio(0);

    int t = 1;
    // cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}