Problem Description

A directed graph is termed semi-connected if for all pairs of nodes (u, v) where uv, 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:

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, vN. In addition, 2 ≤ X ≤ 1018 and 0 < EN(N-1).

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

Subtask 2 (29%): 0 < N ≤ 10000, 0 < E ≤ 106.

Subtask 3 (52%): 0 < N, E ≤ 106.

Subtask 4 (0%): Sample Testcase

Sample Testcase


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