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 1

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 2

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 3

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 4

Here is the graph given in the input:

This graph satisfies subtask 3.