Maximum Semi‐Connected Subgraph

A directed graph \(G = (V, E)\) is said to be semi‐connected if for every pair of vertices \(u, v \in V\), either there exists a path from \(u\) to \(v\) or from \(v\) to \(u\). A graph \(G' = (V', E')\) is called an induced subgraph of \(G\) if \(V' \subseteq V\) and \(E'\) includes every edge in \(E\) whose both endpoints belong to \(V'\). If an induced subgraph \(G'\) is semi‐connected then it is called a semi‐connected subgraph of \(G\). Among all semi‐connected subgraphs of \(G\), one having the maximum number of vertices is called the maximum semi‐connected subgraph.

Given a directed graph \(G\), your task is to determine two numbers:

• \(K\): the number of vertices in a maximum semi‐connected subgraph of \(G\).
• \(C\): the number of different maximum semi‐connected subgraphs (that is, the number of different vertex sets yielding a maximum semi‐connected subgraph). Since \(C\) can be large, output \(C \bmod X\), where \(X\) is a given modulus.

Note: A semi‐connected subgraph must be an induced subgraph. In particular, if two strongly connected components (SCCs) of \(G\) are connected by an edge (in one direction), then their union is semi‐connected. Therefore, the problem essentially reduces to first computing the SCC decomposition, building the corresponding DAG (condensation graph), and then finding a directed path (chain) in the DAG with maximum total weight (where each component's weight is the number of vertices in that component). Also count the number of such maximum-weight paths modulo \(X\).

The input guarantees that \(G\) has at least one vertex and can be disconnected. Vertices are numbered from 1 to \(n\).

inputFormat

The first line contains three integers \(n, m, X\) where \(n\) is the number of vertices, \(m\) is the number of directed edges, and \(X\) is the modulus for the answer.

Each of the next \(m\) lines contains two integers \(u\) and \(v\) indicating there is a directed edge from \(u\) to \(v\).

\(1 \leq u, v \leq n\).

outputFormat

Output two integers separated by a space in one line: \(K\) and \(C \bmod X\). \(K\) is the maximum number of vertices in a semi‐connected subgraph and \(C\) is the count of different maximum semi‐connected subgraphs modulo \(X\).

sample

3 3 100
1 2
2 3
1 3

3 1