#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

#define int long long
const int MOD = 1e9 + 7;

bool get_bit(int x, int d) {
	return x >> d & 1;
}

struct DSU {
	vector <int> p;
	vector <int> sz;
	int n;

	DSU(int n) {
		this->n = n;
		p.resize(n);
		for (int i = 0; i < n; i++) {
			p[i] = i;
		}
		sz.resize(n, 1);
	}

	int get(int x) {
		if (p[x] == x) return x;
		return p[x] = get(p[x]);
	}

	bool merge(int x, int y) {
		x = get(x);
		y = get(y);
		if (x == y) return 0;
		if (sz[x] > sz[y]) {
			swap(x, y);
		}
		p[x] = y;
		sz[y] += sz[x];
		return 1;
	}

	DSU() {}
};

DSU dsu;

int n, m, G;
vector <vector <int>> g;
vector <vector <int>> cg;
vector <pair <int, int>> eds;

int T;
vector <int> used;

bool dfs(int v, int target, int a, int b) {
	if (v == target) return 1;
	if (used[v] == T) return 0;
	used[v] = T;
	for (auto u : g[v]) {
		if (v == a && u == b) continue;
		if (dfs(u, target, a, b)) return 1;
	}
	return 0;
}

bool check(int v, int u, int a, int b) {
	T++;
	return dfs(v, u, a, b);
}

signed main() {
	cin >> n >> m >> G;
	g.resize(n);
	cg.resize(n);
	used.resize(n);
	T = 1;
	vector <vector <bool>> can(n, vector <bool>(n));
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		a--; b--;
		g[a].push_back(b);
		eds.push_back({ a, b });
	}
	for (auto [a, b] : eds) {
		can[a][b] = check(a, b, a, b);
		can[b][a] = check(b, a, a, b);
	}

	dsu = DSU(n);
	for (auto [a, b] : eds) {
		if (can[b][a]) {
			dsu.merge(a, b);
		}
	}
	vector <int> deg_cin(n);
	vector <int> deg_cout(n);
	int cnt = 0;
	for (auto [a, b] : eds) {
		if (dsu.get(a) != dsu.get(b)) {
			if (can[a][b]) {
				cnt++;
			}
		}
		else {
			cg[a].push_back(b);
			deg_cout[a]++;
			deg_cin[b]++;
		}
	}
	vector <vector <int>> cmpvs(n);
	for (int i = 0; i < n; i++) {
		cmpvs[dsu.get(i)].push_back(i);
	}
	int prod = 1;
	for (int cmpi = 0; cmpi < n; cmpi++) {
		if (cmpvs[cmpi].empty()) continue;
		auto vs = cmpvs[cmpi];
		bool passis = 1;
		for (auto v : vs) {
			if (deg_cin[v] != 1 || deg_cout[v] != 1) {
				passis = 0;
			}
		}
		if (passis) {
			prod *= (int)vs.size();
			prod %= MOD;
			cnt += vs.size() - 1;
			continue;
		}
		for (auto bv : vs) {
			if (deg_cin[bv] != 1 || deg_cout[bv] != 1) {
				for (auto v : cg[bv]) {
					if (deg_cin[v] == 1 && deg_cout[v] == 1) {
						int cv = v;
						int len = 1;
						while (deg_cin[cv] == 1 && deg_cout[cv] == 1) {
							cv = cg[cv][0];
							len++;
						}
						prod *= len;
						prod %= MOD;
						cnt += len - 1;
					}
				}
			}
		}
	}
 
	cout << cnt << '\n' << -1;
}