首先缩点
然后半连通其实就是缩点后节点数最多的链
注意这里一定是一条链才一定是半连通
然后重建图拓扑排序上做dp即可
type node=record
po,next:longint;
end; var w,e:array[..] of node;
rd,be,c,f,g,p,q,st,dfn,low:array[..] of longint;
v:array[..] of boolean;
s,mo,i,n,m,x,y,j,h,t,ans1,ans2,len:longint; function min(a,b:longint):longint;
begin
if a>b then exit(b) else exit(a);
end; procedure fadd(x,y:longint);
begin
inc(len);
w[len].po:=y;
w[len].next:=q[x];
q[x]:=len;
end; procedure add(x,y:longint);
begin
inc(len);
e[len].po:=y;
e[len].next:=p[x];
p[x]:=len;
end; procedure tarjan(x:longint);
var i,y:longint;
begin
inc(h);
dfn[x]:=h;
low[x]:=h;
inc(t);
st[t]:=x;
v[x]:=true;
i:=p[x];
while i<> do
begin
y:=e[i].po;
if dfn[y]= then
begin
tarjan(y);
low[x]:=min(low[x],low[y]);
end
else if v[y] then low[x]:=min(low[x],low[y]);
i:=e[i].next;
end;
if dfn[x]=low[x] then
begin
inc(s);
while st[t+]<>x do
begin
y:=st[t];
v[y]:=false;
inc(c[s]);
be[y]:=s;
dec(t);
end;
end;
end; begin
readln(n,m,mo);
for i:= to m do
begin
readln(x,y);
add(x,y);
end;
for i:= to n do
if dfn[i]= then
begin
h:=;
t:=;
tarjan(i);
end; len:=;
for i:= to n do
begin
j:=p[i];
while j<> do
begin
y:=e[j].po;
if be[y]<>be[i] then
begin
fadd(be[i],be[y]);
inc(rd[be[y]]);
end;
j:=e[j].next;
end;
end;
t:=;
for i:= to s do
if rd[i]= then
begin
inc(t);
st[t]:=i;
f[i]:=c[i];
g[i]:=;
end;
h:=;
fillchar(low,sizeof(low),);
while h<=t do
begin
x:=st[h];
i:=q[x];
while i<> do
begin
y:=w[i].po;
dec(rd[y]);
if rd[y]= then
begin
inc(t);
st[t]:=y;
end;
if low[y]<>x then
begin
low[y]:=x;
if f[y]<f[x]+c[y] then
begin
f[y]:=f[x]+c[y];
g[y]:=g[x];
end
else if f[y]=f[x]+c[y] then g[y]:=(g[y]+g[x]) mod mo;
end;
i:=w[i].next;
end;
inc(h);
end;
ans1:=;
ans2:=;
for i:= to s do
if f[i]>ans1 then
begin
ans1:=f[i];
ans2:=g[i];
end
else if f[i]=ans1 then ans2:=(ans2+g[i]) mod mo;
writeln(ans1);
writeln(ans2);
end.