Problem Description
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.
Input
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.
Output
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.
Limits
For all testcases, nodes are labelled from 1 to N. Hence, 1 ≤ u, v ≤ N. In addition, 2 ≤ X ≤ 1018 and 0 < E ≤ N(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
Input
6 6 20070603
1 2
2 1
1 3
2 4
5 6
6 4
Output
3
3