#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#ifndef DEBUG
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#endif

using namespace __gnu_pbds;

template<typename T>
using oset = tree<T, null_type, std::less<T>, rb_tree_tag, tree_order_statistics_node_update>;
using ll = int;
using pll = std::pair<ll, ll>;
using ld = long double;
using i128 = __int128;

#define lv(v) v + 1
#define rv(v) v + 2 * (m - l)

std::mt19937 rnd(std::chrono::steady_clock::now().time_since_epoch().count());

std::vector<std::vector<ll>> G, G1;
std::vector<ll> ord, used;
ll cntcmp = 0;
std::vector<std::vector<ll>> comps;

void dfs(ll v, bool flg = false){
    used[v] = 1;
    if (flg){
        comps.back().push_back(v);
        for(auto u : G1[v]){
            if (!used[u]){
                dfs(u, flg);
            }
        }
    }
    if (!flg){
        for(auto u : G[v]){
            if (!used[u]){
                dfs(u, flg);
            }
        }
        ord.push_back(v);
    }
}

void dfs1(ll v){

}

std::vector<std::vector<ll>> compp(){
    ord.clear();
    comps.clear();
    used.assign(G.size(), 0);
    G1.clear();
    G1.resize(G.size());
    for (int i = 0; i < G.size(); ++i) {
        if (!used[i]){
            dfs(i);
        }
    }
    for(int i = 0; i < G.size(); ++i){
        for(auto u : G[i]){
            G1[u].push_back(i);
        }
    }
    std::reverse(ord.begin(), ord.end());
    used.assign(G.size(), 0);
    cntcmp = 0;
    for (int i = 0; i < G.size(); ++i) {
        if (!used[ord[i]]){
            comps.push_back({});
            dfs(ord[i], 1);
        }
    }
    std::vector<ll> razb(G.size());
    for (int i = 0; i < comps.size(); ++i) {
        for (auto u : comps[i]) {
            razb[u] = i;
        }
        comps[i].clear();
    }
    std::vector<ll> zam(G.size(), -1);
    ll l = 0;
    for (int i = 0; i < G.size(); ++i) {
        if (zam[razb[i]] == -1){
            zam[razb[i]] = l;
            razb[i] = l++;
        }
        else{
            razb[i] = zam[razb[i]];
        }
    }
    for (int i = 0; i < G.size(); ++i) {
        comps[razb[i]].push_back(i);
    }
    return comps;
}

void solve() {
    ll n, m, g;
    std::cin >> n >> m >> g;
    G.resize(n);
    used.resize(n);
    std::vector<pll> rebr;
    for (int i = 0; i < m; ++i) {
        ll v, u;
        std::cin >> v >> u;
        --v, --u;
        G[v].push_back(u);
        rebr.push_back({v, u});
    }
    auto iskk = compp();
    ll ans = 0, cntans = 1;
    std::vector<ll> dp(1ll << m);
    dp[0] = 1;
    for (int msk = 0; msk < 1ll << m; ++msk) {
        ll cnt = 0;
        G.clear();
        G.resize(n);
        for (int j = 0; j < m; ++j) {
            if ((msk >> j) & 1){
                ++cnt;
                G[rebr[j].second].push_back(rebr[j].first);
            }
            else{
                G[rebr[j].first].push_back(rebr[j].second);
            }
        }
        ll b = (iskk == compp());
        if (!b){
            bool flg = true;
            for (int i = 0; i < m; ++i) {
                if ((msk >> i) & 1){
                    ll ms1 = (1ll << m) - 1;
                    ms1 -= 1ll << i;
                    if (!dp[(msk & ms1)]){
                        flg = false;
                    }
                }
            }
            if (!flg){
                continue;
            }
            dp[msk] = 1;
            if (ans == cnt){
                ++cntans;
            }
            else if (cnt > ans){
                ans = cnt;
                cntans = 1;
            }
        }
    }
    std::cout << ans <<'\n'<<cntans;
}

int main() {
#ifdef DEBUG
    std::freopen("/home/olymp/CLionProjects/untitled/input.txt", "r", stdin);
#endif
    std::cin.tie(0)->std::ios::sync_with_stdio(0);
    int tt = 1;
//    std::cin >> tt;
    while (tt--) {
        solve();
    }
}
