問題文

カトー君と、友人であるシンヤ君は、昨年末に発売された、とある大人気アクションゲームを二人でプレイするのが大好きです。

このゲームには \(N\) 種類のキャラがおり、それぞれのキャラに \(1,2, \cdots ,N\) の番号が割り振られています。そして、お互いのプレイヤーが \(1\) キャラずつを選び、対戦します。また、それぞれのキャラには他のキャラに対する相性が存在しています。

相性は全部で \(3\) 種類あり、"有利"、"不利"、"五分"のいずれかです。

• キャラ \(i\) が キャラ \(j\) に有利であるとき
  • 相手がキャラ \(j\) を選んでいて、自分がキャラ \(i\) を選んだ場合、対戦を有利に進めることができます。
• キャラ \(i\) が キャラ \(j\) に不利であるとき
  • 相手がキャラ \(j\) を選んでいて、自分がキャラ \(i\) を選んだ場合に、苦戦を強いられてしまいます。
• キャラ \(i\) と キャラ \(j\) が五分であるとき
  • 相性に左右されない公平な対戦をすることができます。

また、キャラ \(i\) が キャラ \(j\) に有利であるときは、必ずキャラ \(j\) が キャラ \(i\) に不利となっています。

さて、カトー君は負けず嫌いなため、シンヤ君に負けないように一部のキャラに絞って練習をすることにしました。

具体的には、ある区間 \([L,R]\) を選択して、その区間内のキャラを練習します。

また、より有利に試合を進めるために、次の条件を満たす区間を選ぶことにしました。

• 相手がいかなるキャラを選んでも、そのキャラに対して五分、もしくは有利なキャラが少なくとも一体は存在する。ただし、相手と同じキャラはその候補から除外する。

普段は勉強で忙しいカトー君は、できるだけ練習するキャラの数を少なくしたいです。忙しいカトー君の代わりに、練習するキャラを選んであげてください。

制約

• \(2 \leq N \leq 10^5\)
• \(1 \leq M \leq \min(2 \times 10^5,N(N-1)/2)\)
  • 有利不利の相性の個数を表す。
• \(1 \leq a_i, b_i \leq N\)
  • \(a_i \neq b_i\)
  • キャラ \(a_i\) は キャラ \(b_i\) に有利であることを表す。
• 問題文の条件と矛盾する入力は与えられないことが保証される。すなわち、
  • \(i \neq j\) ならば \((a_i,b_i) \neq (a_j,b_j) \) (同じ条件は二度出現しない)
  • \(i \neq j\) ならば \((a_i,b_i) \neq (b_j,a_j) \) (正反対の条件が同時に入力されることはない)
  が成り立つ。
• 入力される値はすべて整数である。
• なお、入力で与えられなかった相性については、全て五分であることが保証される。

入力例 1

3
2
2 1
3 1

出力例 1

2 3

例えば、キャラ \(1\) と \(3\) に対してはキャラ \(2\) を、キャラ \(2\) に対してはキャラ \(3\) を選択することで、任意の相手キャラに対して五分以上の相性で対戦することができます。

入力例 2

3
2
1 2
3 2

出力例 2

1 3

例えば、キャラ \(1\) と \(2\) に対してはキャラ \(3\) を、キャラ \(3\) に対してはキャラ \(1\) を選択することで、任意の相手キャラに対して五分以上の相性で対戦することができます。

また、区間の中で、一度も選ばれないキャラが存在していても構いません。

入力例 3

3
2
2 1
2 3

出力例 3

-1

キャラ \(2\) に対して五分以上の相性となるキャラは存在しません。

入力例 4

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

出力例 4

1 3