CPC '21 Contest 1 P4 - AQT and Directed Graph

View as PDF

Points: 12 (partial)
Time limit: 2.0s
Python 3.0s
Memory limit: 256M
Python 512M

Authors:
Problem type

AQT is studying directed graphs and has encountered the following problem: given a directed graph consisting of nodes with labels and edges, find a pair of vertices such that and is reachable from . Can you help him find such a pair in the graph (or output -1 if none exists)?

Constraints    If a directed edge connecting node to exists in the input, the edge connecting node to node is guaranteed to be in the input as well.

The graph will have no cycles.

Input Specification

The first line will contain the integers , the number of vertices in the graph, and , the number of edges in the graph.

The next lines will each contain a directed edge in the form of space-separated integers , denoting an edge from node to . For all pairs , .

Output Specification

Output a pair such that and is reachable from . If there exist multiple answers, output the one that maximizes , and then if there are multiple answers with maximum .

5 5
1 4
2 5
3 1
2 4
1 2

3 5

Explanation

Here is the graph given in the input: The pairs of vertices such that and is reachable from are:

• • • • • • • The output is thus 3 5 as maximizes , then .

This graph also satisfies subtask 3.

5 5
4 3
5 2
3 1
4 2
5 1

-1

Explanation

Here is the graph given in the input: There are no pairs of vertices such that and is reachable from , so the output is -1.

This graph also satisfies subtask 3.

4 6
3 1
1 2
3 2
2 1
2 3
1 3

2 3

Explanation

Here is the graph given in the input: 6 6
6 4
4 1
6 1
3 2
2 5
3 5

3 5

Explanation

Here is the graph given in the input: 