#include <bits/stdc++.h>
using namespace std;
#ifdef _LOCAL
#define debug(x) cerr << __LINE__ << ' ' << __PRETTY_FUNCTION__ << ": " << x << '\n';
#else
#define debug(...) 238;
#endif
mt19937 rng(238);
mt19937_64 rng64(238);
using ll = long long;
template <typename T, int U>
using ar = array<T, U>;
template <typename T, typename U>
bool chmin(T& x, const U&& y) {
    if (x > y) {
        x = y;
        return true;
    }
    return false;
}
template <typename T, typename U>
bool chmax(T& x, const U&& y) {
    if (x < y) {
        x = y;
        return true;
    }
    return false;
}

#include <ext/pb_ds/assoc_container.hpp>
template <typename T>
using ordered_set = __gnu_pbds::tree<T, __gnu_pbds::null_type,
                                     less<T>,
                                     __gnu_pbds::rb_tree_tag,
                                     __gnu_pbds::tree_order_statistics_node_update>; 

constexpr int Inf = 0x3f3f3f3f;
constexpr ll  inf = 0x3f3f3f3f3f3f3f3f;

const int maxn = 2005;
array<vector<int>, maxn> g;
array<bool, maxn> used;

bool verify(int v, int u) {
    used[v] = true;
    if (v == u) {
        return true;
    }
    for (int k : g[v]) {
        if (used[k]) {
            continue;
        }
        if (verify(k, u)) {
            return true;
        }
    }
    return false;
}

/*

so fine after we find scc we can just multiply all the scc answers

how to solve for scc?

on cycle there's only one way to rebuild scc
we can leave any edge and there will be one way to complete scc
so for n-vertex cycle answer is      {n - 1, n}

ok fine then we have node connected to two edge independent cycles
then answer is obv                   {n + m - 2, n * m}

so we can somehow using biconnected type shit solve this??
sounds right

scc is actually some cycles sitting on one another
so whats next

if edge is sitting on a couple of paths (v,u) (u,v)
we need to know its direction

if theres only like (v,u) type paths direction is implicitly
defined yep

thats it?

*/

void solve() {
    int n, m, gr;
    cin >> n >> m >> gr;
    vector<pair<int, int>> edges;
    for (int v, u, i = 0; i < m; ++i) {
        cin >> v >> u;
        --v, --u;
        g[v].push_back(u);
        edges.emplace_back(v, u);
    }

    int ans = 0;
    for (auto [v, u] : edges) {
        used.fill(false);
        // if (verify(u, v)) {
        if (true) {
            g[v].erase(find(g[v].begin(), g[v].end(), u));
            
            used.fill(false);
            bool fw = verify(v, u);
            used.fill(false);
            bool bw = verify(u, v);

            ans += fw ^ bw;

            g[v].push_back(u);
        } else {
            g[v].erase(find(g[v].begin(), g[v].end(), u));
            
            used.fill(false);
            ans += verify(v, u);

            g[v].push_back(u);
        }
    }

    cout << ans - 1 << '\n' << 1;
}

int main() {
#ifdef _LOCAL
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    cin.tie(0)->sync_with_stdio(0);

    int Tc = 1;
    // cin >> Tc;
    while (Tc--) {
        solve();
        cout << '\n';
    }

    return 0;
}