
#include "bits/stdc++.h"

using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
#define ve vector
#define pb push_back
#define all(a) a.begin(), a.end()
using ld = double;
#define int ll
mt19937 rnd(321932);

template<class A>
istream &operator>>(istream &in, ve<A> &a) {
    for (auto &x: a)
        in >> x;
    return in;
}

template<class A>
ostream &operator<<(ostream &out, ve<A> a) {
    for (auto &x: a)
        out << x << ' ';
    return out << '\n';
}

ve<int> x;

struct lct {
    int n;

    struct func {
        ld a, b;

        int get(int i) const {
            return (floor)(a * x[i] + b);
        }
    };

    ve<func> t;

    void add(int v, int l, int r, func nw) {
        int m = (l + r) / 2;
        auto &old = t[v];
        if (old.get(m) < nw.get(m))
            swap(old, nw);
        if (l + 1 == r)
            return;
        if (nw.get(l) >= old.get(l))
            add(2 * v + 1, l, m, nw);
        else if (nw.get(r - 1) >= old.get(r - 1))
            add(2 * v + 2, m, r, nw);
    }

    void add(ld a, ld b) {
        add(0, 0, n, {a, b});
    }

    void add(int v, int l, int r, int ql, int qr, func nw) {
        if (l >= qr || ql >= r)
            return;
        if (ql <= l && r <= qr) {
            add(v, l, r, nw);
            return;
        }
        int m = (l + r) / 2;
        add(2 * v + 1, l, m, ql, qr, nw);
        add(2 * v + 2, m, r, ql, qr, nw);
    }

    void add(int l, int r, ld a, ld b) {
        add(0, 0, n, l, r, {a, b});
    }

    int get(int v, int l, int r, int i) {
        if (l + 1 == r)
            return t[v].get(i);
        int m = (l + r) / 2;
        if (i < m)
            return max(t[v].get(i), get(2 * v + 1, l, m, i));
        else
            return max(t[v].get(i), get(2 * v + 2, m, r, i));
    }

    int get(int i) {
        return (int) get(0, 0, n, i);
    }

    lct() {
        n = x.size();
        t.assign(4 * n, {0, -1e18});
    }
};
ve<set<int>> g;
ve<set<int>> _g;
ve<int> top;
ve<int> used;
int timer = 0;
void dfs(int v) {
    used[v] = timer;
    for (auto &u : g[v]) {
        if (used[u] != timer)
            dfs(u);
    }
    top.pb(v);
}

void _dfs(int v, ve<int> &cmp, int t) {
    cmp[v] = t;
    used[v] = timer;
    for (auto &u : _g[v]) {
        if (used[u] != timer)
            _dfs(u, cmp, t);
    }
}

ve<int> find_cmp() {
    int n= g.size();
    ve<int> cmp(n);
    ++timer;
    top.clear();
    for (int i = 0; i < n; ++i) {
        if (used[i] != timer)
            dfs(i);
    }
    ++timer;
    int cnt = 0;
    reverse(all(top));
    for (auto &u : top) {
        if (used[u] != timer) {
            _dfs(u, cmp, cnt++);
        }
    }
    return cmp;
}

int32_t main() {
#ifdef DEBUG
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n, m, G;
    cin >> n >> m >> G;
    g.resize(n);
    _g = g;
    used.assign(n, -1);
    ve<pll> edges;
    for (int i = 0; i < m; ++i) {
        int x, y;
        cin >> x >> y;
        edges.pb({x-1, y-1});
        g[x-1].insert(y-1);
        _g[y-1].insert(x-1);
    }
    ve<int> cmp(n);
    ++timer;
    top.clear();
    for (int i = 0; i < n; ++i) {
        if (used[i] != timer)
            dfs(i);
    }
    ++timer;
    int cnt = 0;
    reverse(all(top));
    for (auto &u : top) {
        if (used[u] != timer) {
            _dfs(u, cmp, cnt++);
        }
    }
    int ans_1 = 0, ans_2 = 0;
    for (int mask = 0; mask < (1 << m); ++mask) {
        ve<int> pos;
        for (int i = 0; i < m; ++i) {
            if ((mask >> i) & 1)
                pos.pb(i);
        }
        int cnt = 0;

        for (int nwmask = 0; nwmask < (1 << (int)(pos.size())); ++nwmask) {
            auto pred_g = g, pred__g = _g;
            for (int j = 0; j < pos.size(); ++j) {
                if ((nwmask >> j) & 1) {
                    g[edges[pos[j]].first].erase(edges[pos[j]].second);
                    _g[edges[pos[j]].first].insert(edges[pos[j]].second);
                    g[edges[pos[j]].second].insert(edges[pos[j]].first);
                    _g[edges[pos[j]].second].erase(edges[pos[j]].first);
                }
            }
            auto c = find_cmp();
            bool flag = 1;
            for (int i = 0; i < n; ++i) {
                for (int j = 0; j < n; ++j) {
                    if (cmp[i] == cmp[j] && c[i] != c[j]) {
                        flag = 0;
                        break;
                    }
                    if (c[i] == c[j] && cmp[i] != cmp[j]) {
                        flag = 0;
                        break;
                    }
                }

            }
            if (flag) {
                cnt++;
            }

            g = pred_g;
            _g = pred__g;
            if (cnt > 1)
                break;
        }
        if (cnt == 1) {
            if (ans_1 < pos.size()) {
                ans_1 = pos.size();
                ans_2 = 1;
            } else if (ans_1 == pos.size()) {
                ans_2++;
            }
        }
    }
    cout << ans_1 << '\n' << ans_2;
}
