赵灵儿 @ 2018-04-03 19:45:45
#include <bits/stdc++.h>
using namespace std;
namespace program {
typedef long long big;
big next[1000005], to[1000005], head[1000005], Head[1000005], To[1000005], Next[1000005], Stack[100005], cnt, top, pre[100005], low[100005], query[100005], dp[100005];
big tot1, tot2, now, cssno[100005], size[100005];
big n, m, Mod, xx, yy, dis[100005], f[100005], MAXN, ans;
template <class T>
T read() {
T s = 0;
int ch;
while (!isdigit(ch = getchar()));
do
s = s* 10 + ch - '0';
while (isdigit(ch = getchar()));
return s;
}
void add(big x, big y) {
tot1 += 1;
next[tot1] = head[x];
to[tot1] = y;
head[x] = tot1;
}
void Add(big x, big y) {
tot2 += 1;
Next[tot2] = Head[x];
To[tot2] = y;
Head[x] = tot2;
}
inline void dfs(big k) {
cnt += 1;
pre[k] = low[k] = cnt;
top += 1;
Stack[top] = k;
for (big i = head[k]; i; i = next[i]) {
big oo = to[i];
if (!pre[oo]) {
dfs(oo);
low[k] = min(low[k], low[oo]);
} else {
if (!cssno[oo])
low[k] = min(low[k], low[oo]);
}
}
if (low[k] == pre[k]) {
now += 1;
while (top) {
big oo = Stack[top--];
cssno[oo] = now;
size[now] += 1;
if (oo == k)
break;
}
}
return;
}
void work() {
n = read<big>();
m = read<big>();
Mod = read<big>();
for (big i = 1 ; i <= m; i++) {
xx = read<big>();
yy = read<big>();
add(xx, yy);
}
for (big i = 1; i <= n; i++) {
if (!pre[i])
dfs(i);
}
for (big i = 1; i <= n; i++) {
for (big j = head[i]; j; j = next[i]) {
big oo = cssno[to[j]], ooo = cssno[i];
if (oo != ooo)
Add(ooo, oo), dis[oo] += 1;
}
}
big vis[10005] = {0};
big l = 1, r = 0;
for (big i = 1; i <= now ; i++) {
if (!dis[i])
f[i] = size[i], dp[i] = 1, query[++r] = i;
}
while (l <= r) {
big k = query[l], oo;
for (big i = Head[k]; i ; i = Next[i]) {
oo = To[i];
dis[oo] -= 1;
if (!dis[oo])
query[++r] = oo;
if(vis[oo] == k)
continue;
if (size[oo] + f[k] == f[oo])
dp[oo] = (dp[oo] + dp[k]) % Mod;
if (size[oo] + f[k] > f[oo]) {
f[oo] = f[k] + size[oo];
dp[oo] = dp[k] % Mod;
}
vis[oo] = k;
}
l += 1;
}
for (big i = 1; i <= now; i++) {
if (f[i] == MAXN)
ans = (ans + dp[i]) % Mod;
if (f[i] > MAXN)
MAXN = f[i], ans = dp[i] % Mod;
}
cout << MAXN << '\n' << ans << '\n';
return;
}
}
int main() {
program::work();
return 0;
}