#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <unordered_map>
#include <map>
#include <random>
#include <chrono>

#define int long long

using namespace std;

vector<vector<int>> g;
vector<vector<int>> gr;
vector<bool> used;
vector<bool> used1;
vector<int> comps;
vector<int> ord;
//map<int, vector<int>> KCC;
int n, m;

const int MOD = 1e9 + 7;

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

void dfs1(int u, int cmp) {
    used1[u] = true;
    comps[u] = cmp;
    //KCC[cmp].push_back(u);
    for (auto v : gr[u]) {
        //cout << "reversed edge " << u << ' ' << v << '\n';
        if (!used1[v]) {
            dfs1(v, cmp);
        }
    }
}

int getkcc(vector<pair<int, int>> edges) {
    ord.clear();
    g.clear();
    gr.clear();
    used.clear();
    used1.clear();
    comps.clear();
    g.resize(n);
    gr.resize(n);
    used.resize(n, false);
    used1.resize(n, false);
    comps.resize(n);
    for (int i = 0; i < m; i++) {
        int u,v;
        u = edges[i].first;
        v = edges[i].second;
        g[u].push_back(v);
        gr[v].push_back(u);
    }
    for (int i = 0; i < n; i++) {
        if (!used[i]){
            dfs(i);
        }
    }
    reverse(ord.begin(), ord.end());
    int comp = 0;
    for (auto u : ord) {
        if (!used1[u]) {
            dfs1(u, comp);
            comp++;
        }
    }
    return comp;
}

signed main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    vector<int> pow(30);
    pow[0] = 1;
    for (int i = 1; i < 30; i++) {
        pow[i] = 2*pow[i-1];
    }
    int gg;
    cin >> n >> m >> gg;
    vector<pair<int,int>> edges(m);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        u--;
        v--;
        edges[i] = {u,v};
    }
    int comp = getkcc(edges);
    int ans = 0;
    int maxsz = 0;
    vector<int> correct = comps;
    vector<vector<int>> ks(comp);
    for (int i = 0; i < n; i++) {
        ks[comps[i]].push_back(i);
    }
    sort(ks.begin(), ks.end());
    for (int mask = 0; mask < pow[m]; mask++) {
        //1 - стираем
        bool flag = true;
        int mm = mask;
        int bits = 0;
        while (mm != 0) {
            if (mm % 2 == 1) {
                bits++;
            }
            mm /= 2;
        }
        /*if (mask == 48) {
            cout << bits << "!!!!!!!!!!!!!!\n";
        }*/
        for (int mask1 = 0; mask1 < pow[bits]; mask1++) {
            //1 - меняем
            /*if (mask == 48 && mask1 == 1) {
                cout << "aaaaaaaaaa\n";
            }*/
            vector<pair<int, int>> edges1(m);
            int cnt = 0;
            for (int i = 0; i < m; i++) {
                if ((mask >> i) & 1) {
                    if ((mask1 >> cnt) & 1) {
                        edges1[i] = {edges[i].second, edges[i].first};
                        /*if (mask == 48 && mask1 == 1) {
                            cout << "edge" << edges1[i].first << ' ' << edges1[i].second << '\n';
                        }*/
                    } else {
                        edges1[i] = edges[i];
                    }
                    cnt++;
                } else {
                    edges1[i] = edges[i];
                }
            }
            int comp1 = getkcc(edges1);
            vector<vector<int>> ks1(comp1);
            for (int i = 0; i < n; i++) {
                ks1[comps[i]].push_back(i);
            }
            sort(ks1.begin(), ks1.end());
            /*if (mask == 48 && mask1 == 1) {
                for (auto p : edges1) {
                    cout << p.first + 1<< ' ' << p.second + 1<< '\n';
                }
                cout << "_____________";
                for (auto e : comps) {
                    cout << e << ' ' ;
                }
                cout << '\n';
                cout << "____________";
            }*/
            if (ks == ks1 && edges1 != edges) {
                /*for (auto e : comps) {
                    cout << e << ' ' ;
                }
                cout << '\n';
                 */
                flag = false;
            }
        }
        if (flag) {
            ans++;
            maxsz = max(maxsz,bits);
            //cout << mask << '\n';
        }
    }
    cout << maxsz << '\n' << ans;
    return 0;
}


