semiconnected

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:

  • 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, 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

Input

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

Output

3
3

Submitting to 'semiconnected'


You're not logged in! Click here to login


Submitting to 'semiconnected'


You're not logged in! Click here to login


Submitting .cpp to 'semiconnected'


You're not logged in! Click here to login

Time Limit: 1 Seconds
Memory Limit: 1024MB
No. of ACs: 3
Your best score: 0
Source: Dunjudge Archive

Subtask Score
1 19
2 29
3 52
4 0