A directed graph is termed *semi-connected* if for all pairs of nodes (*u*, *v*) where *u* ≠ *v*, there is at least a directed path from *u* to *v* or a directed path from *v* to *u*.

A graph *G'* with *N'* nodes and *E'* edges is considered as a vertex-induced subgraph of *G* with *N* nodes and *E* edges if the following conditions are fulfilled:

*N'*is a subset of*N*. In other words, all nodes in subgraph*G'*are in*G*.*E'*is the set of all edges of the graph*G*whose endpoints are both in the subset*N'*.

Given a graph *G* with *N* nodes and *E* edges, find a semi-connected, vertex-induced subgraph of *G* with the largest number of nodes, *K*.
Also, count how many distinct semi-connected, vertex-induced subgraphs that can be formed from graph *G* that also has the largest number of nodes *K*.
Two vertex-induced subgraphs are considered distinct if the composition of nodes differ between the sub-graphs.
As this result can be very large, output the count modulo *X*.

First line of input contains 3 integers: *N*, *E* and *X*.

*E* lines of input will follow, with each line containing 2 integers, *u* and *v*. This indicates that there is a directed edge from node *u* to node *v*. It is guaranteed that there will not be more than one line with the same *u* and *v*.

On the first line of output, you are to output the largest number of nodes in a semi-connected vertex-induced subgraph, *K*.

On the second line of output, you are to output the number of distinct semi-connected vertex-induced subgraphs of *G* that also have *K* nodes.

For all testcases, nodes are labelled from 1 to *N*. Hence, 1 ≤ *u*, *v* ≤ *N*. In addition, 2 ≤ *X* ≤ 10^{18} and 0 < *E* ≤ *N*(*N*-1).

Subtask 1 (19%): 0 < *N*, *E* ≤ 150.

Subtask 2 (29%): 0 < *N* ≤ 10000, 0 < *E* ≤ 10^{6}.

Subtask 3 (52%): 0 < *N*, *E* ≤ 10^{6}.

Subtask 4 (0%): Sample Testcase

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

3 3

Subtask | Score |
---|---|

1 | 19 |

2 | 29 |

3 | 52 |

4 | 0 |