#pragma GCC optimize("O3,unroll-loops")

#include <bits/stdc++.h>

using namespace std;
using ll = long long int;
using ull = unsigned long long int;

#define all(x) (x).begin(), (x).end()
#define rall(X) (x).rbegin(), (x).rend()

vector<int> ord;
vector<bool> used;
vector<vector<int>> g;
vector<vector<int>> tg;

void dfs(int u)
{
    used[u] = true;
    for (int v : g[u])
    {
        if (!used[v])
            dfs(v);
    }
    ord.push_back(u);
}

void dfs2(int u, int clr, vector<int> &color)
{
    color[u] = clr; 
    for (int v : tg[u])
    {
        if (color[v] == -1)
            dfs2(v, clr, color);
    }
}

vector<int> condense(int n, vector<array<int, 2>> &e)
{
    ord.clear();
    tg.clear();
    g.clear();
    used.clear();
    used.resize(n);
    g.resize(n);
    tg.resize(n);

    for (auto [u, v] : e)
    {
        g[u].push_back(v);
        tg[v].push_back(u);
    }

    for (int i = 0; i < n; i++)
    {
        if (!used[i])
            dfs(i);
    }
    reverse(all(ord));

    vector<int> color(n, -1);
    int clr = 0;
    for (int i : ord)
    {
        if (color[i] == -1)
            dfs2(i, clr++, color);
    }

    vector<int> ch(clr, -1);
    for (int i = 0; i < n; i++)
    {
        if (ch[color[i]] == -1)
            ch[color[i]] = i;
        color[i] = ch[color[i]];
    }
    return color;
}

void solve()
{
    int n, m, G;
    cin >> n >> m >> G;


    vector<array<int, 2>> e(m);
    for (int i = 0; i < m; i++)
    {
        cin >> e[i][0] >> e[i][1];
        --e[i][0];
        --e[i][1];
    }
    
    vector<int> x = condense(n, e);
    vector<bool> var(1 << m, true);
    for (int mask = (1 << m) - 2; mask >= 0; mask--)
    {
        auto e2 = e;
        for (int i = 0; i < m; i++)
        {
            if (((mask >> i) & 1) == 0)
                swap(e2[i][0], e2[i][1]);
        }

        if (condense(n, e2) == x)
        {
            var[mask] = false;
            continue;
        }
        for (int i = 0; i < m; i++)
        {
            if (((mask >> i) & 1) == 0)
            {
                if (!var[mask ^ (1 << i)])
                {
                    var[mask] = false;
                    break;
                }
            }
        }
    }

    int ans_sz = 0;
    int ans_cnt = 0;

    for (int mask = 0; mask < (1 << m); mask++)
    {
        int sz = m - __builtin_popcount(mask);
        if (!var[mask])
            continue;

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

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

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
#ifdef LOCAL
    freopen("C:/work/Day 2/in.txt", "r", stdin);
    freopen("C:/work/Day 2/out.txt", "w", stdout);
    cin >> t;
#else
    t = 1;
#endif

    while (t--)
        solve();
    return 0;
}
