36分求调

#include <stdio.h>
#include <stack>
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
#include <utility>

using std::stack;
using std::vector;
using std::min;
using std::max;
using std::queue;
using std::map;
using std::pair;
using std::make_pair;

#define N 100001

vector <int> V[N], U[N];

int DFN[N], Low[N], Index, Color[N], sccnt, dp[N], Group[N], r[N], Max;
long long Sum[N], Ans;

bool Exist[N];

stack <int> S;

queue <int> Q;

map <pair<int, int>, bool> M;

void Tarjan(int u)
{
	DFN[u] = Low[u] = ++ Index;
	
	S.push(u);
	
	Exist[u] = true;
	
	for(int v : V[u])
	{
		if(!DFN[v])
		{
			Tarjan(v);
			
			Low[u] = min(Low[u], Low[v]);
		}
		else if(Exist[v])
			Low[u] = min(Low[u], DFN[v]);
	}
	
	int v;

 	if(DFN[u] == Low[u])
	{
	    ++ sccnt;
	    do
		{ 
	      	v = S.top();
	      	
	     	Exist[v] = false;
	     	
	     	S.pop();
	     	
	     	Color[v] = sccnt;
	     	
	     	++ Group[sccnt];
	    }while (u != v);
  	}
}

int n, m, x[1000001], y[1000001], X;

int main()
{
	scanf("%d%d%d", &n, &m, &X);
	
	for(int i = 0; i != m; ++ i)
	{
		scanf("%d%d", x + i, y + i);
		
		V[x[i]].push_back(y[i]);
	}
	
	for(int i = 1; i <= n; ++ i)
		if(!DFN[i])
			Tarjan(i);
	
 	for(int i = 1; i <= m; i++)
   	 	if (Color[x[i]] != Color[y[i]] && !M[make_pair(Color[x[i]], Color[y[i]])])
   	 	{
   	 		M[make_pair(Color[x[i]], Color[y[i]])] = true;
   	 		
     		U[Color[x[i]]].push_back(Color[y[i]]);
     		
     		++ r[Color[y[i]]];
   	 	}
    
    for(int i = 1; i <= sccnt; ++ i)
    {
		if(!r[i])
		{
			Sum[i] = 1;
			
 		   	Q.push(i);
    
   			dp[i] = Group[i];			
		}
	}
    
 	while(!Q.empty())
 	{
 		const int b = Q.front();
 		
 		Q.pop();
 		
 		for(int i = 0; i != U[b].size(); ++ i)
 		{
 			if(dp[U[b][i]] < dp[b] + Group[U[b][i]])
 			{
 				dp[U[b][i]] = dp[b] + Group[U[b][i]];
 				
 				Sum[U[b][i]] = Sum[b];
 				
 				Q.push(U[b][i]);
 			}
 			else if(dp[U[b][i]] == dp[b] + Group[U[b][i]])
 			{
			 	Sum[U[b][i]] += Sum[b];
			 	
			 	Sum[U[b][i]] %= X;
			}
 		}
 	}  
 	
 	/*for(int i = 1; i <= sccnt; ++ i)
 	{
	 	for(int j = 0; j != U[i].size(); ++ j)
	 		printf("%d %d\n", i, U[i][j]);
	}
 	
 	for(int i = 1; i <= sccnt; ++ i)
 		printf("%d ", dp[i]);*/
 		
 	for(int i = 1; i <= sccnt; ++ i)
 		Max = max(Max, dp[i]);
 	
 	for(int i = 1; i <= sccnt; ++ i)
 		if(dp[i] == Max)
 		{
 			Ans += Sum[i];
 			Ans %= X;
 		}
 			
	printf("%lld\n%lld", Max, Ans);
}