#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using pp = pair<int, int>;
using ld = long double;

template <typename T>
istream &operator>>(istream &s, vector<T> &a)
{
    for (T &el : a)
    {
        s >> el;
    }
    return s;
}

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

int n, m, g;
int timer = 0;

void dfs(int v, vector<vector<int>> &graph, vector<int> &used, vector<int> &tout)
{
    used[v] = true;
    for (int to : graph[v])
    {
        if (!used[to])
        {
            dfs(to, graph, used, tout);
        }
    }
    tout[v] = timer;
    timer++;
}

void dfs2(int v, vector<vector<int>> &graph, vector<int> &used, vector<int> &lst)
{
    lst.push_back(v);
    used[v] = true;
    for (int to : graph[v])
    {
        if (!used[to])
        {
            dfs2(to, graph, used, lst);
        }
    }
}

vector<int> count_css(vector<vector<int>> &graph)
{
    vector<vector<int>> rgraph(n);
    for (int v = 0; v < n; v++)
    {
        for (int to : graph[v])
        {
            rgraph[to].push_back(v);
        }
    }
    vector<int> used(n, false), tout(n, 0);
    for (int v = 0; v < n; v++)
    {
        if (!used[v])
        {
            dfs(v, graph, used, tout);
        }
    }
    vector<int> nodes(n);
    iota(nodes.begin(), nodes.end(), 0);
    sort(nodes.begin(), nodes.end(), [&](int a, int b)
         { return tout[a] > tout[b]; });
    used.assign(n, 0);
    vector<int> col(n, 0);
    for (int v : nodes)
    {
        if (!used[v])
        {
            vector<int> lst;
            dfs2(v, rgraph, used, lst);
            int cl = *min_element(lst.begin(), lst.end());
            for (int nd : lst)
            {
                col[nd] = cl;
            }
        }
    }
    return col;
}

void solve()
{
    cin >> n >> m >> g;
    vector<pp> edges(m);
    for (int i = 0; i < m; i++)
    {
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        edges[i] = {a, b};
    }
    vector<int> des_css(n, -1);
    vector<bool> is_good(1 << m, true);
    for (int mask = 0; mask < (1 << m); mask++)
    {
        vector<vector<int>> graph(n);
        for (int i = 0; i < m; i++)
        {
            if (((mask >> i) & 1) == 0)
            {
                graph[edges[i].first].push_back(edges[i].second);
            }
            else
            {
                graph[edges[i].second].push_back(edges[i].first);
            }
        }
        vector<int> curr = count_css(graph);
        if (mask == 0)
        {
            des_css = curr;
        }
        else
        {
            if (des_css == curr)
            {
                is_good[mask] = false;
            }
        }
    }
    for (int mask = 0; mask < (1 << m); mask++)
    {
        for (int bt = 0; bt < m; bt++)
        {
            if (((mask >> bt) & 1) == 1)
            {
                if (!is_good[mask ^ (1 << bt)])
                {
                    is_good[mask] = false;
                }
            }
        }
    }
    int ans = 0, cnt = 0;
    for (int mask = 0; mask < (1 << m); mask++)
    {
        if (is_good[mask])
        {
            int curr = __builtin_popcount(mask);
            if (curr > ans)
            {
                ans = curr;
                cnt = 1;
            }
            else if (curr == ans)
            {
                cnt++;
            }
        }
    }
    cout << ans << '\n'
         << cnt;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    solve();
}