题目连通：传送门
思路：
题目定义很清晰，然后就不会了QAQ……
后来看了书，先缩点，然后再用拓扑排序找到最长的链子的节点数（因为缩点后所有点都是一个强连通分量，所以找最长的链子就是最大限度包含
点的半连通子图）然后用dp求出由多少个长度相同的链子（e数组记录从开始到i节点所有的方案数，dis数组表示链子的节点个数，每次找到更长的链子时就更新数组，然后最后求出多少个满足最长链子的方案）。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 1e6+;
int head[maxn],next[maxn],ver[maxn],tot;
int num[maxn],low[maxn],tim,co[maxn],si[maxn],col;
int st[maxn],que[maxn],top,t,w;
int du[maxn],e[maxn],ans,anss,m,n,MOD;
int x[maxn],y[maxn],nu[maxn],dis[maxn];
int MIN(int a,int b)
{
return a<b?a:b;
}
void addedge(int u,int v)
{
ver[++tot]=v;next[tot]=head[u];head[u]=tot;
}
void Tarjan(int u)
{
low[u]=num[u]=++tim;
st[++top]=u;
for(int i=head[u];i;i=next[i]){
int v=ver[i];
if(!num[v]){
Tarjan(v);
low[u]=MIN(low[u],low[v]);
}
else if(!co[v]) low[u]=MIN(low[u],num[v]);
}
if(num[u]==low[u]){
col++;
si[col]++;
co[u]=col;
while(u!=st[top]){
si[col]++;
co[st[top]]=col;
top--;
}
top--;
}
}
bool cmp(int a,int b)
{
if(x[a]!=x[b]) return x[a]<x[b];
else return y[a]<y[b];
}
void Remove()
{
for(int i=;i<=m;i++){
nu[i]=i;
x[i]=co[x[i]];
y[i]=co[y[i]];
}
sort(nu+,nu++m,cmp);
}
void Build()
{
tot=;
memset(head,,sizeof(head));
for(int i=;i<=m;i++){
int z=nu[i];
if((x[z]!=y[z])&&(x[z]!=x[nu[i-]]||y[z]!=y[nu[i-]]))
addedge(x[z],y[z]),du[y[z]]++;
}
}
void Reset()
{
for(int i=;i<=col;i++)
if(!du[i]){
que[++w]=i;
dis[i]=si[i];
e[i]=;
if(dis[i]>dis[ans]) ans=i;
}
}
void Topo()
{
while(t<w){
int u=que[++t];
for(int i=head[u];i;i=next[i]){
int v=ver[i];
--du[v];
if(dis[v]<dis[u]+si[v]){
dis[v]=dis[u]+si[v];
e[v]=;
if(dis[ans]<dis[v]) ans=v;
}
if(dis[v]==dis[u]+si[v]) e[v]=(e[v]+e[u])%MOD;
if(!du[v]) que[++w]=v;
}
}
}
void ANS()
{
for(int i=;i<=n;i++)
if(dis[i]==dis[ans]) anss=(anss+e[i])%MOD;
}
int main(void)
{
int i,j;
scanf("%d%d%d",&n,&m,&MOD);
for(i=;i<=m;i++){
scanf("%d%d",&x[i],&y[i]);
addedge(x[i],y[i]);
}
for(i=;i<=n;i++)
if(!num[i]) Tarjan(i); Remove();
Build();
Reset();
Topo();
ANS();
printf("%d\n%d",dis[ans],anss);
return ;
}