## 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 .

If no answer exists, output -1 instead.

#### Sample Input 1

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

#### Sample Output 1

3 5

#### Explanation 1

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.

#### Sample Input 2

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

#### Sample Output 2

-1

#### Explanation 2

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.

#### Sample Input 3

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

#### Sample Output 3

2 3

#### Explanation 3

Here is the graph given in the input: #### Sample Input 4

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

#### Sample Output 4

3 5

#### Explanation 4

Here is the graph given in the input: 