Problem Description

Kato and his friend Shinyo love playing a certain popular action game that was released at the end of last year.

In this game, there are \(N\) characters, each assigned a number from \(1, 2, \cdots, N\). Players choose one character each and then battle against each other. Each character has a compatibility against other characters, which can be either "advantageous," "disadvantageous," or "even."

• When character \(i\) is advantageous against character \(j\):
• If the opponent chooses character \(j\) and you choose character \(i\), you can advance the battle advantageously.
• When character \(i\) is disadvantageous against character \(j\):
• If the opponent chooses character \(j\) and you choose character \(i\), you will be forced into a tough battle.
• When character \(i\) and character \(j\) are even:
• You can have a fair battle without being influenced by compatibility.

Additionally, when character \(i\) is advantageous against character \(j\), character \(j\) is always disadvantageous against character \(i\).

Since Kato hates losing, he decided to focus his practice on a subset of characters to avoid losing to Shinyo.

Specifically, he will choose an interval \([L, R]\) and practice the characters within this interval.

To advance the match more advantageously, he decided to choose an interval that satisfies the following condition:

• No matter which character the opponent chooses, there is at least one character within the interval \([L, R]\) that is either even or advantageous against that character. However, the same character as the opponent's choice is excluded from this consideration.

Kato, who is usually busy with studies, wants to minimize the number of characters he practices. Please choose the characters for him to practice.

Input Format

The input is given from the standard input in the following format:

\(N\)
\(M\)
\(a_1\) \(b_1\)
\(a_2\) \(b_2\)
\(\vdots\)
\(a_M\) \(b_M\)

Output Format

Output the endpoints \(L, R\) \((L \leq R)\) of the smallest interval that satisfies the problem's conditions, separated by a space. If there are multiple intervals with the smallest width, output the one with the smallest \(L\) value.

If there is no such interval, output -1.

\(L\) \(R\)

Sample Input and Output

Sample Input #1

3
2
2 1
3 1

Sample Output #1

2 3

Sample Input #2

3
2
1 2
3 2

Sample Output #2

1 3

Sample Input #3

3
2
2 1
2 3

Sample Output #3

-1

Sample Input #4

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

Sample Output #4

1 3

Notes/Hints

Constraints

• \(2 \leq N \leq 10^5\)
• \(1 \leq M \leq \min(2 \times 10^5, N(N-1)/2)\)
• Represents the number of advantageous/disadvantageous compatibilities.
• \(1 \leq a_i, b_i \leq N\)
• \(a_i \neq b_i\)
• Character \(a_i\) is advantageous against character \(b_i\).
• The input is guaranteed to not contradict the problem statement, i.e.,
• If \(i \neq j\), then \((a_i, b_i) \neq (a_j, b_j)\) (the same condition does not appear twice)
• If \(i \neq j\), then \((a_i, b_i) \neq (b_j, a_j)\) (opposite conditions are not given simultaneously)
• All input values are integers.
• Any compatibility not given in the input is guaranteed to be even.

Sample Explanation 1

For example, by choosing character \(2\) against characters \(1\) and \(3\), and character \(3\) against character \(2\), you can battle any opponent character with an even or advantageous compatibility.

Sample Explanation 2

For example, by choosing character \(3\) against characters \(1\) and \(2\), and character \(1\) against character \(3\), you can battle any opponent character with an even or advantageous compatibility. It's also okay if some characters within the interval are never chosen.

Sample Explanation 3

There is no character that is even or advantageous against character \(2\).

见题面 Input 部分

见题面 Output 部分