// i must be the reason why
// you have given up your smiles
// and the hope inside your life has been stolen
// i must be the reason why
// you have told me all these lies
// that i will lead a happier life without you by my side
// дальше текст забыл

// t.me/truebaza <---- лучший тг канал
// t.me/truebaza <---- лучший тг канал
// t.me/truebaza <---- лучший тг канал
// t.me/truebaza <---- лучший тг канал
// t.me/truebaza <---- лучший тг канал
// t.me/truebaza <---- лучший тг канал
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
#define fastio cin.tie(0), ios_base::sync_with_stdio(false)
#define all(x) (x).begin(), (x).end()
#define INF 1000

vector<vector<int>> g;
vector<bool> visited;

bool reach(int v, int w) {
    if (v == w) {
        return true;
    }
    visited[v] = true;
    for (auto we : g[v]) {
        if (!visited[we] && reach(we, w)) {
            return true;
        }
    }
    return false;
}

vector<int> ts;
int vis = 0;
void dfs(int v) {
    vis |= (1ll << v);
    for (auto w : g[v]) {
        if (!(vis & (1ll << w))) dfs(w);
    }
    ts.push_back(v);
}
vector<vector<int>> rg;

vector<int> curcomp;

void dfs2(int v) {
    vis |= (1ll << v);
    curcomp.push_back(v);
    for (auto w : rg[v]) {
        if (!(vis & (1ll << w))) {
            dfs2(w);
        }
    }
}

vector<vector<int>> get_css() {
    ts.clear();
    vis = 0;
    for (int i = 0; i < g.size(); ++i) {
        if (!(vis & (1ll << i))) {
            dfs(i);
        }
    }
    rg.assign(g.size(), {});
    for (int v = 0; v < g.size(); ++v) {
        for (auto w : g[v]) {
            rg[w].push_back(v);
        }
    }
    vis = 0;
    vector<vector<int>> res;
    reverse(all(ts));
    for (auto v : ts) {
        if (!(vis & (1ll << v))) {
            curcomp.clear();
            dfs2(v);
            sort(all(curcomp));
            res.push_back(curcomp);
        }
    }
    sort(all(res));
    return res;
}

bool there[1ll << 20];

auto main() -> signed { // t.me/truebaza <---- лучший тг канал,
    fastio;
    for (auto& i : there) i = false;
    int n, m, KEK;
    cin >> n >> m >> KEK;
    vector<vector<int>> oldg(n);
    g.resize(n);
    oldg.resize(n);
    vector<pair<int, int>> edges;
    for (int i = 0; i < m; ++i) {
        int v, w;
        cin >> v >> w;
        v--, w--;
        oldg[v].push_back(w);
        edges.push_back({v, w});
    }
    swap(g, oldg);
    auto cur = get_css();
    swap(g, oldg);
    int res = -INF, cnt = 0;
    visited.resize(n);
    vector<int> allowed;
    for (int mask = 1; mask < (1ll << m); ++mask) {
        if (__builtin_popcount(mask) > 16) continue;
        bool can = true;
        g.assign(n, {});
        for (int j = 0; j < m; ++j) {
            if (mask & (1ll << j)) {
                g[edges[j].second].push_back(edges[j].first);
            } else {
                g[edges[j].first].push_back(edges[j].second);
            }
        }
        auto cc = get_css();
        if (cc == cur) there[(1ll << m) - 1 - mask] = true;
    }
    for (int msk = (1ll << m) - 1; msk >= 1; --msk) {
        if (!there[msk]) continue;
        for (int j = 0; j < m; ++j) {
            if (msk & (1ll << j)) {
                there[msk - (1ll << j)] = true;
            }
        }
    }
    for (int msk = 0; msk < (1ll << m); ++msk) {
        if (m - __builtin_popcount(msk) < res) continue;
        int x = m - __builtin_popcount(msk);
        if (!there[msk]) {
            if (x > res) res = x, cnt = 0;
            cnt++;
        }
    }
    cout << res << '\n' << cnt << '\n';
}