#include <bits/stdc++.h>

using namespace std;


const short maxn = 100;

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

void dfst(short v)
{
    vis[v] = 1;
    for(auto u:g[v])
    {
        if(!vis[u])
        {
            dfst(u);
        }
    }
    ts.push_back(v);
    return ;
}
void dfs2(short v,short c)
{
    comp[v] = c;
    vis[v] = 1;
    for(auto u:ig[v])
    {
        if(!vis[u])
        {
            dfs2(u,c);
        }
    }
    return ;
}
void 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)
    {
        short 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(int i = 0;i < n;++i)
        vis[i] =0;
    comp.clear();
    comp.resize(n);
    short yk = 0;
    reverse(ts.begin(),ts.end());

    for(short j = 0;j < n;++j)
    {
        if(!vis[ts[j]])
        {
            dfs2(ts[j],yk++);
        }
    }
    vector<short> 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 ;
}

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});
    }
    getc(0);
    vector<short> obr = comp;
    for(int i =1;i < (1<<m);++i)
    {
        getc(i);
        if(comp == 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;
}
