semiconnected

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 ≤ 10¹⁸ and 0 < E ≤ N(N-1).

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

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

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

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