#include "bits/extc++.h"

using namespace std;
using namespace __gnu_pbds;

using ll = long long;

template<typename T>
istream &operator>>(istream &is, vector<T> &a);

template<typename T>
ostream &operator<<(ostream &os, vector<T> &a);


using ordered_set = tree<int, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update>;

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, G;
    cin >> n >> m >> G;

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

        g[u - 1].push_back(v - 1);
        gv[v - 1].push_back(u - 1);
    }

    vector<int> comp(n, -1);
    {
        vector<int> used(n);
        vector<int> topsort;
        function<void(int)> dfs = [&](int v) -> void {
            used[v] = true;
            for (auto u: g[v]) {
                if (used[u]) continue;
                dfs(u);
            }
            topsort.push_back(v);
        };
        for (int i = 0; i < n; ++i) {
            if (!used[i]) dfs(i);
        }

        std::reverse(topsort.begin(), topsort.end());

        int cm = 0;
        function<void(int)> dfs2 = [&](int v) -> void {
            comp[v] = cm;
            for (auto u: gv[v]) {
                if (comp[u] != -1) continue;
                dfs2(u);
            }
        };

        for (auto v: topsort) {
            if (comp[v] == -1) {
                dfs2(v);
                cm++;
            }
        }
    }

    // ui < vi

    vector<vector<int>> can(n, vector<int>(n));
    for (int i = 0; i < n; ++i) {
        deque<int> q;
        q.push_back(i);
        while (!q.empty()) {
            int v = q.front();
            q.pop_front();

            can[i][v] = true;
            for (auto u: g[v]) {
                if (can[i][u]) continue;
                q.push_back(u);
            }
        }
    }

    vector<vector<int>> matrix(n, vector<int>(m));
    for (int v = 0; v < n; ++v) {
        for (auto u: g[v]) matrix[v][u] = true;
    }

    int cnt = 0;

    for (int u = 0; u < n; ++u) {
        for (int v = 0; v < n; ++v) {
            if (u == v) continue;
            if (!matrix[u][v]) continue;
            for (auto k: g[u]) {
                if (k==v)continue;
                if (can[k][v] && matrix[u][v]) {
                    cnt++;
                    break;
                }
            }
        }
    }

    cout << cnt << "\n";
    cout << 1 << "\n";
}

template<typename T>
istream &operator>>(istream &is, vector<T> &a) {
    for (auto &v: a) is >> v;
    return is;
}

template<typename T>
ostream &operator<<(ostream &os, vector<T> &a) {
    for (auto v: a) os << v << " ";
    return (os << "\n");
}