Largest Semi-Connected Subgraph

Problem Source

ZJOI2007

Problem Description

A directed graph $G = (V, E)$ is called semi-connected if: for all $u, v \in V$, either $u \to v$ or $v \to u$, i.e. for any two vertices $u, v$ in the graph there is a directed path from $u$ to $v$ or from $v$ to $u$.

If $G' = (V', E')$ satisfies $V' \subset V$ and $E'$ consists of all edges in $E$ related to $V'$, then $G'$ is called an induced subgraph of $G$. If $G'$ is an induced subgraph of $G$ and is semi-connected, then $G'$ is a semi-connected subgraph of $G$.

If $G'$ is the semi-connected subgraph of $G$ containing the most vertices, then $G'$ is the largest semi-connected subgraph. Given a directed graph $G$, find $K$, the number of vertices in the largest semi-connected subgraph of $G$, and $C$, the number of different largest semi-connected subgraphs. Since $C$ may be large, only output $C \bmod X$.

Input Format

The first line contains three integers $N, M, X$. $N, M$ are the number of vertices and edges of $G$; the meaning of $X$ is as above.

The next $M$ lines each contain two positive integers $a, b\ (1 \le a, b \le N)$, representing a directed edge $(a, b)$.

There are no multiple edges in the input. $N \le 10^5,\ M \le 10^6,\ X \le 10^8$.

Output Format

Two lines in total. The first line contains one integer $K$; the second line contains $C \bmod X$.

Sample Input

6 6 20070603
1 2
2 1
1 3
2 4
5 6
6 4

Sample Output

3
3