#include <bits/stdc++.h>

using namespace std;
#define int int64_t
const int mod = 1e9 + 7;
void solve() {
    int n, m, number;
    cin >> n >> m >> number;
    vector<pair<int,int> > edge(m);
    vector<vector<int> > a(n + 1);
    for (int i = 0; i < m; i++) {
        cin >> edge[i].first >> edge[i].second;
        a[edge[i].first].push_back(edge[i].second);
    }
    vector<vector<bool> > get(n + 1, vector<bool> (n + 1, false));
    for (int i = 1; i <= n; i++) {
        deque<int> d;
        d.push_back(i);
        get[i][i] = true;
        while (d.size() > 0) {
            int v = d.front();
            d.pop_front();
            for (int j = 0; j < a[v].size(); j++) {
                int u = a[v][j];
                if (get[i][u] == true) {
                    continue;
                }
                get[i][u] = true;
                d.push_back(u);
            }
        }
    }
    /*
    for (int i = 1; i <= n; i++) {
        for (int l = i + 1; l <= n; l++) {
            cout << i << " " << l << ' ' << get[i][l] + get[l][i] << endl;
        }
    }
    */
    int ans = 0, kol = 1;
    for (int i = 1; i < (1 << m); i++) {
        vector<int> g(0);
        for (int j = 0; j < m; j++) {
            if ((i & (1 << j)) == 0) {
                continue;
            }
            g.push_back(j);
        }

        int t = 1;
        for (int j = 1; j < (1 << int(g.size())); j++) {
            vector<vector<int> > b(n + 1);
            for (int s = 0; s < m; s++) {
                if ((i & (1 << s)) == 0) {
                    b[edge[s].first].push_back(edge[s].second);
                    continue;
                }
            }
            for (int l = 0; l < g.size(); l++) {
                if ((j & (1 << l)) == 0) {
                    b[edge[g[l]].first].push_back(edge[g[l]].second);
                }
                if ((j & (1 << l)) == (1 << l)) {
                    b[edge[g[l]].second].push_back(edge[g[l]].first);
                }
            }

            vector<vector<bool> > get2(n + 1, vector<bool> (n + 1, false));
            for (int l = 1; l <= n; l++) {
                deque<int> d;
                d.push_back(l);
                get2[l][l] = true;

                while (d.size() > 0) {
                    int v = d.front();
                    d.pop_front();
                    for (int s = 0; s < b[v].size(); s++) {
                        int u = b[v][s];
                        if (get2[l][u] == true) {
                            continue;
                        }
                        get2[l][u] = true;
                        d.push_back(u);
                    }
                }

            }

            bool us = true;
            for (int l = 1; l <= n; l++) {

                for(int k = l + 1; k <= n; k++) {
                    if (get[l][k] + get[k][l] == 2 && get2[l][k] + get2[k][l] <= 1) {
                        us = false;
                        break;
                    }

                    if (get[l][k] + get[k][l] <= 1 && get2[l][k] + get2[k][l] == 2) {
                        us = false;
                    }
                }

            }

            if (us == true) {
                t++;
                break;
            }
        }

        if (t >= 2) {
            continue;
        }
        if (g.size() == ans) {
            kol++;
        }
        if (g.size() > ans) {
                /*
            for (int j = 0; j < g.size(); j++) {
                cout << g[j] << " ";
            }
            */
            ans = g.size();
            kol = 1;
        }
    }
    cout << ans << " " << kol;
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
}





