oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

semiconnected Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

semiconnected.html

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

Tags

ZJOI 2007

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
11951s128MBMinimum
22971s128MBMinimum
352111s128MBMinimum
4011s128MBMinimum

Judge Compile Command

g++-8 ans.cpp -o semiconnected -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.