Description

Original source: ZJOI 2007

A directed graph $G = (V,E)$ is called Semi-Connected if for every pair of vertices $u,v\in V$, there exists either a directed path from $u$ to $v$ or a directed path from $v$ to $u$. In other words, for any two vertices $u$ and $v$ in the graph, there is at least one directed path connecting them in some direction.

If $G'=(V',E')$ satisfies that $E’$ consists of all edges in $E$ that are incident to vertices 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 referred to as a semi-connected subgraph of $G$. If $G’$ is a semi-connected subgraph of $G$ with the maximum number of vertices, then $G’$ is called a maximum semi-connected subgraph of $G$.

Given a directed graph $G$, determine the number of vertices $K$ in its maximum semi-connected subgraph and the number of distinct maximum semi-connected subgraphs $C$. Since $C$ might be very large, only output the remainder of $C$ divided by $X$.

Input Format

The first line contains three integers $N, M, X$. Here, $N$ and $M$ represent the number of vertices and edges in graph $G$, respectively, and $X$ is the modulus as described above.

The next $M$ lines each contain two integers $a$ and $b$, indicating a directed edge $(a, b)$.

Each vertex in the graph is labeled from $1$ to $N$. It is guaranteed that no duplicate edges $(a,b)$ will appear in the input.

Output Format

The output should consist of two lines. The first line contains the integer $K$, and the second line contains $C \bmod X$.

Sample 1

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

3
3

Constraints & Hints

For $20\%$ of the data, $N \le 18$; For $60\%$ of the data, $N \le 10^4$; For $100\%$ of the data, $1\le N \le 10^5$, $1\le M \le 10^6$, and $X\le 10^8$.