#include <bits/stdc++.h>

using namespace std;

template<typename T>
istream& operator>>(istream& is, vector<T>& a) {
    for (auto& x : a) is >> x;
    return is;
}
template<typename T>
ostream& operator<<(ostream& is, vector<T>& a) {
    for (auto& x : a) is << x << ' ';
    cout << '\n';
    return is;
}

template<typename T1, typename T2>
istream& operator>>(istream& is, vector<pair<T1, T2>>& a) {
    for (auto& x : a) is >> x.first >> x.second;
    return is;
}

template<typename T1, typename T2>
ostream& operator<<(ostream& is, vector<pair<T1, T2>>& a) {
    for (auto& x : a) is << x.first << ' ' << x.second << '\n';
    return is;
}


template<typename T1, typename T2>
void amax(T1& a, T2 b) {
    a = max(a, b);
}
template<typename T1, typename T2>
void amin(T1& a, T2 b) {
    a = min(a, b);
}
#ifdef OTKR
bool local = true;
#else
bool local = false;
#endif // OTKR

#define int long long
#define sz(x) (int)(x.size())
#define all(x) x.begin(), x.end()
#define ff first
#define ss second
#define pb emplace_back
#define push emplace

void solve();
void stress();
void precalc();

using vi = vector<int>;
using pi = pair<int, int>;
using vpi = vector<pi>;
using vvi = vector<vi>;
using vvpi = vector<vpi>;

const int ma = 3e5;
const int INF = 1e18;
const int mod = 1e9 + 7;

struct Mint{
    int x;
    Mint() : x(0) {}
    Mint(int x) : x(x) {}
    Mint operator+(const Mint& b) const {
        int res = x + b.x;
        if (res >= mod) res -= mod;
        return {res};
    }
    Mint operator-(const Mint& b) const {
        int res = x - b.x;
        if (res < 0) res += mod;
        return {res};
    }
    Mint operator*(const Mint& b) const {
        return {x * b.x % mod};
    }
    Mint operator==(const Mint& b) const {
        return x == b.x;
    }
};

struct Segtree{
    struct Node{
        int su;
        int mi;
        int indmi;
        Node operator+(const Node& b) const {
            Node res;

            return res;
        }
    };
    Node Make(int x, int i) {
        Node res;

        return res;
    }
    Node N;
    vector<Node> t;
    void build(int v, int l, int r,const vi& a) {
        if (l + 1 == r) {
            t[v] = Make(a[l], l);
        }
        int m = (l + r) / 2;
        build(v * 2, l, m, a);
        build(v * 2 + 1, m, r, a);
        t[v] = t[v * 2] + t[v * 2 + 1];
    }
    Segtree(const vi& a) : t(4 * sz(a)) {
        build(1, 0, sz(a), a);
    }
    void upd(int v, int l, int r, int i, int x) {
        if (l + 1 == r) {
            t[v] = Make(x, l);
        }
        int m = (l + r) / 2;
        if (i < m) {
            upd(v * 2, l, m, i, x);
        } else {
            upd(v * 2 + 1, m, r, i, x);
        }
        t[v] = t[v * 2] + t[v * 2 + 1];
    }
    Node get(int v, int nl, int nr, int ql, int qr) {
        if (nl >= qr || nr <= ql) return N;
        if (ql <= nl && nr <= qr) return t[v];
        int m = (nl + nr) / 2;
        return get(v * 2, nl, m, ql, qr) + get(v * 2 + 1, m, nr, ql, qr);
    }
};

signed main() {
    if (local) {
        freopen("input.txt", "r", stdin);
    }
    int t = 1; //cin >> t;
    while (t--) {
        solve();
    }
}

mt19937 mt(time(0));

void brut(int n, int m, int k, int q, vi& a) {
    int cnt = 0;
    multiset<int> mp;
    for (auto& x : a) mp.insert(x);
    for (int t = 0; t < m; t++) {
        vi dop;
        for (int j = 0; j < k; j++) {
            int f = *mp.rbegin();
            dop.pb(f - 1);
            mp.erase(prev(mp.end()));
        }
        for (auto x : dop) {
            mp.insert(x);
        }
    }
    for (auto x : mp) {
        cout << x << ' ';
    }
}

vi brut1(int n, int m,vi& a) {
    //k == 1
    sort(all(a));
    if (m == 0) {
        return a;
    }
    int cnt = 1, cur = a.back();
    a.pop_back();
    for ( ; m != 0 && cnt != n; ) {
        int ne = a.back();
        int ost = (cnt * (cur - ne));
        if (ost <= m) {
            cnt++;
            m -= ost;
            cur = ne;
            a.pop_back();
        } else {
            vi ans;
            for (auto x : a) {
                ans.pb(x);
            }
            int cn = m / cnt;
            int os = m % cnt;
            m = 0;
            for (int k = 0;k < os; k++) {
                ans.pb(cur - cn - 1);
            }
            for (int k = 0; k < (cnt - os); k++) {
                ans.pb(cur - cn);
            }
            cnt = n;
            return ans;
        }
    }
    if (m != 0) {
        vi ans;
        for (auto x : a) {
            ans.pb(x);
        }
        int cn = m / cnt;
        int os = m % cnt;
        m = 0;
        for (int k = 0;k < os; k++) {
            ans.pb(cur - cn - 1);
        }
        for (int k = 0; k < (cnt - os); k++) {
            ans.pb(cur - cn);
        }
        cnt = n;
        return ans;
    }
}

void stress() {
    for (int we = 0; we <= 1e5; we++) {
        int n = mt() % 10 + 1;
        int m = mt() % 100;

    }
}

void dfs(int v, vvi& adj, vi& us, vi& top) {
    us[v] = 1;
    for (auto x : adj[v]) {
        if (us[x]) continue;
        dfs(x, adj, us, top);
    }
    top.pb(v);
}
int cv = 1;
void dfs2(int v, vvi& radj, vi& c) {
    c[v] = cv;
    for (auto x : radj[v]) {
        if (!c[x]) {
            dfs2(x, radj, c);
        }
    }
}

vvi kompa(int n, vvi& adj, vvi& radj) {
    vi us1(n);
    vi top;
    for (int i = 0; i < n; i++) {
        if (!us1[i]) {
            dfs(i, adj, us1, top);
        }
    }
    reverse(all(top));
    vi c(n);
    cv = 1;
    for (auto x : top) {
        if (!c[x]) {
            dfs2(x, radj, c);
            cv++;
        }
    }
    vvi k2(n);
    for (int i = 0; i < n; i++) {
        k2[c[i] - 1].pb(i);
    }
    for (auto& x : k2) {
        sort(all(x));
    }
    sort(all(k2));
    return k2;
}

void solve() {
    int n, m, g; cin >> n >> m >> g;
    vpi r(m);
    vvi adj1(n), radj1(n);
    for (int i = 0; i < m; i++) {
        int x, y; cin >> x >> y;
        adj1[--x].pb(--y);
        radj1[y].pb(x);
        r[i] = {x, y};
    }
    vvi cvNEED = kompa(n, adj1, radj1);
    int maxx = 0, cnt = 0;
    for (int ma = 0; ma < (1 << m); ma++) {
        vi cu;
        for (int i = 0; i < m; i++) {
            int t = (ma >> i) & 1;
            if (t) cu.pb(i);
        }
        if (sz(cu) <= maxx) continue;
        int is = 0;
        for (int mask = 0; mask < (1 << (sz(cu))); mask++) {
            vvi adj2(n), radj2(n);
            int cu2 = 0, f = 0;
            for (int i = 0; i < m; i++) {
                int t1 = (ma >> i) & 1;
                auto [x, y] = r[i];
                if (!t1) {
                    adj2[x].pb(y);
                    radj2[y].pb(x);
                } else {
                    int t2 = (mask >> cu2) & 1;
                    if (!t2) {
                        f++;
                        adj2[x].pb(y);
                        radj2[y].pb(x);
                    } else {
                        adj2[y].pb(x);
                        radj2[x].pb(y);
                    }
                    cu2++;

                }
            }
            vvi cv2 = kompa(n, adj2, radj2);
            if (cv2 == cvNEED) {
                is++;
                if (is >= 2) {
                    break;
                }
            }
        }
        if (is == 1) {
            if (maxx < sz(cu)) {
            cnt = 1;
                maxx = sz(cu);
            } else if (maxx == sz(cu)) {
                  cnt++;
            }
        }
    }
    cout << maxx << '\n';
    cout << cnt;
}









