#include <bits/stdc++.h>

using namespace std;

const int maxn = 100;

vector<pair<int,int>> r;
vector<vector<int>> g;
vector<vector<int>> ig;
vector<int> comp;
vector<int> ts;
vector<int> vis;
int n;
int mm[1<<20];

void dfst(int v)
{
    vis[v] = 1;
    for(auto u:g[v])
    {
        if(!vis[u])
        {
            dfst(u);
        }
    }
    ts.push_back(v);
    return ;
}
void dfs2(int v,int c)
{
    comp[v] = c;
    vis[v] = 1;
    for(auto u:ig[v])
    {
        if(!vis[u])
        {
            dfs2(u,c);
        }
    }
    return ;
}
vector<int> getc(int mask)
{
    vis.clear();
    vis.resize(n);
    g.clear();
    g.resize(n);
    ts.clear();
    ig.clear();
    ig.resize(n);
    int i2 = mask;
    for(int j = 0;j < r.size();++j)
    {
        int u = r[j].first,v = r[j].second;
        if(i2%2)
            swap(u,v);
        g[u].push_back(v);
        ig[v].push_back(u);
        i2/=2;
    }
    for(int i = 0;i < n;++i)
    {
        if(!vis[i])
            dfst(i);
    }
    for(auto & c:vis)
        c = 0;
    comp.clear();
    comp.resize(n);
    int yk = 0;
    reverse(ts.begin(),ts.end());

    for(int j = 0;j < n;++j)
    {
        if(!vis[ts[j]])
        {
            dfs2(ts[j],yk++);
        }
    }
    vector<int> gg(yk,0);
    int tyk = 1;
    for(int j = 0;j < n;++j)
    {
        if(gg[comp[j]])
        {
            comp[j] = gg[comp[j]];
        }
        else
        {
            gg[comp[j]] = tyk++;
            comp[j] = gg[comp[j]];
        }
    }
    return comp;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int m,gg;
    cin >> n >> m >> gg;
    for(int j = 0;j < m;++j)
    {
        int u,v;
        cin >> u >> v;
        u--;
        v--;
        r.push_back({u,v});
    }
    vector<int> obr = getc(0);
    for(int i =1;i < (1<<m);++i)
    {
        if(getc(i) == obr)
        {
            mm[i] = 1;
        }
    }
    for(int j = 0;j < (1<<m);++j)
    {
        for(int i = 0;i < m;++i)
        {
            if(((1<<i) & j))
            {
                mm[j] |= mm[j ^ (1<<i)];
            }
        }
    }
    int mx = 0,cou = 0;
    for(int u = 0;u < (1<<m);++u)
    {
        if(!mm[u])
        {
            int k = __builtin_popcount(u);
            if(k > mx)
            {
                mx = k;
                cou = 1;
            }
            else if(k == mx)
            {
                cou++;
            }
        }
    }
    cout << mx << ' ' << cou << endl;
    return 0;
}
