P2272 [ZJOI2007] Maximum Semi-Connected Subgraph

A directed graph $G=\left(V,E\right)$ is called semi-connected if it satisfies: $\forall u,v\in V$, either $u\to v$ or $v\to u$, that is, for any two vertices $u,v$ in the graph, there exists a directed path from $u$ to $v$ or from $v$ to $u$. If $G'=\left(V',E'\right)$ satisfies $V'\subseteq V$ and $E'$ is the set of all edges in $E$ whose endpoints lie in $V'$, then $G'$ is called an induced subgraph of $G$. If $G'$ is an induced subgraph of $G$ and $G'$ is semi-connected, then $G'$ is called a semi-connected subgraph of $G$. If $G'$ contains the largest number of vertices among all semi-connected subgraphs of $G$, then $G'$ is called a maximum semi-connected subgraph of $G$. Given a directed graph $G$, find $K$, the number of vertices in a maximum semi-connected subgraph of $G$, and $C$, the number of different maximum semi-connected subgraphs. Since $C$ may be large, output $C$ modulo $X$.

The first line contains three integers $N,M,X$. $N$ and $M$ denote the number of vertices and edges of graph $G$, respectively. The meaning of $X$ is as described above. The next $M$ lines each contain two positive integers $a,b$, representing a directed edge $\left(a,b\right)$. Each vertex is labeled $1,2,3\dots N$. It is guaranteed that the same $\left(a,b\right)$ does not appear twice in the input.

Output two lines. The first line contains an integer $K$. The second line contains an integer $C\bmod X$.

For $100\%$ of the testdata, $N\le 10^5$, $M\le 10^6$, $X\le 10^8$. Translated by ChatGPT 5