CPC '21 Contest 1 P4 - AQT and Directed Graph

View as PDF

Submit solution


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 N nodes with labels 1, 2, \dots, N and M edges, find a pair of vertices (x,y) such that x < y and y is reachable from x. Can you help him find such a pair in the graph (or output -1 if none exists)?

Constraints

2 \le N \le 3 \cdot 10^5

1 \le M \le 6 \cdot 10^5

Subtask 1 [5%]

2 \le N \le 5 \cdot 10^3

1 \le M \le 10^4

Subtask 2 [10%]

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

Subtask 3 [15%]

The graph will have no cycles.

Subtask 4 [70%]

No additional constraints.

Input Specification

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

The next M lines will each contain a directed edge in the form of 2 space-separated integers a, b, denoting an edge from node a to b. For all pairs (a,b), a \ne b.

Output Specification

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

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

Here is the graph given in the input:

The pairs of vertices (x,y) such that x < y and y is reachable from x are:

  • (1,2)
  • (1,4)
  • (1,5)
  • (2,4)
  • (2,5)
  • (3,4)
  • (3,5)

The output is thus 3 5 as (3,5) maximizes x, then y.

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

Here is the graph given in the input:

There are no pairs of vertices (x,y) such that x < y and y is reachable from x, 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

Here is the graph given in the input:

This graph satisfies subtask 2.

Sample Input 4

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

Sample Output 4

3 5

Explanation

Here is the graph given in the input:

This graph satisfies subtask 3.


Comments

There are no comments at the moment.