#include "bits/stdc++.h"

using namespace std;

template<class T>
istream& operator>>(istream &is, vector<T> &vec) {
      for (auto &elem: vec) is >> elem;
      return is;
}
template<class T>
ostream& operator<<(ostream &os, const vector<T> &vec) {
      for (auto &elem: vec) os << elem << ' ';
      os << '\n';
      return os;
}

const int N = 3000;
vector<int> g[N], rg[N], used(N), used2(N), ts, comp(N);
set<int> nowcomp;
set<set<int>> comps;

void topsort(int u) {
      used[u] = true;
      for (int v: g[u]) {
            if (!used[v]) topsort(v);
      }
      ts.push_back(u);
}

void dfs2(int u) {
      used2[u] = true;
      nowcomp.insert(u);
      for (int v: rg[u]) {
            if (!used2[v]) dfs2(v);
      }
}

set<set<int>> calc(int n, vector<pair<int, int>> &edges) {
      used.assign(n, 0);
      used2.assign(n, 0);
      comps.clear();
      ts.clear();
      for (int i = 0; i < n; ++i) {
            g[i].clear();
            rg[i].clear();
      }
      for (auto [u, v]: edges) {
            g[u].push_back(v);
            rg[v].push_back(u);
      }
      for (int i = 0; i < n; ++i) {
            if (!used[i]) topsort(i);
      }
      std::reverse(ts.begin(), ts.end());

      int cntcomp = 0;
      vector<int> bad;
      for (int i = 0; i < n; ++i) {
            int u = ts[i];
            if (used2[u]) continue;
            dfs2(u);
            comps.insert(nowcomp);
            nowcomp.clear();
      }
      return comps;
}

signed main() {
#ifdef LOCAL
      freopen("input.txt", "r", stdin);
      freopen("output.txt", "w", stdout);
#else
      ios_base::sync_with_stdio(false);
      cin.tie(nullptr);
#endif
      int n, m, group;
      cin >> n >> m >> group;

      vector<pair<int, int>> edges(m);

      for (int i = 0; i < m; ++i) {
            int u, v;
            cin >> u >> v;

//            if (abs(u - v) == 1 or abs(u - v) == n - 1) {
//                  continue;
//            }

            g[--u].push_back(--v);
            rg[v].push_back(u);
            edges[i] = {u, v};
      }

      auto first = calc(n, edges);

      int mx = 0, cntmx = 1;
      for (int mask = 1; mask < (1 << m) - 1; ++mask) {
            vector<int> ids;
            for (int i = 0; i < m; ++i) {
                  if ((mask >>i) & 1) {
                        ids.push_back(i);
                  }
            }
            int cnt = ids.size();
            int can = 0;
            for (int mask2 = 1; mask2 < (1 << cnt); ++mask2) {
                  for (int i = 0; i < cnt; ++i) {
                        if ((mask2 >> i) & 1) swap(edges[ids[i]].first, edges[ids[i]].second);
                  }
                  auto now = calc(n, edges);
                  if (now == first) {
                        can++;
                        break;
                  }
                  for (int i = 0; i < cnt; ++i) {
                        if ((mask2 >> i) & 1) swap(edges[ids[i]].first, edges[ids[i]].second);
                  }
            }

            if (can == 0) {
                  if (mx == cnt) {
                        cntmx++;
                  } else if (mx < cnt) {
                        cntmx = 1, mx = cnt;
                  }
            }
      }

      cout << mx << ' ' << cntmx << endl;
}