AT_wupc2019_d Choose Your Characters

[problemUrl]: https://atcoder.jp/contests/wupc2019/tasks/wupc2019_d カトー君と、友人であるシンヤ君は、昨年末に発売された、とある大人気アクションゲームを二人でプレイするのが大好きです。 このゲームには \\(N\\) 種類のキャラがおり、それぞれのキャラに \\(1,2, \\cdots ,N\\) の番号が割り振られています。そして、お互いのプレイヤーが \\(1\\) キャラずつを選び、対戦します。また、それぞれのキャラには他のキャラに対する相性が存在しています。 相性は全部で \\(3\\) 種類あり、"有利"、"不利"、"五分"のいずれかです。 - キャラ \\(i\\) が キャラ \\(j\\) に有利であるとき - 相手がキャラ \\(j\\) を選んでいて、自分がキャラ \\(i\\) を選んだ場合、対戦を有利に進めることができます。 - キャラ \\(i\\) が キャラ \\(j\\) に不利であるとき - 相手がキャラ \\(j\\) を選んでいて、自分がキャラ \\(i\\) を選んだ場合に、苦戦を強いられてしまいます。 - キャラ \\(i\\) と キャラ \\(j\\) が五分であるとき - 相性に左右されない公平な対戦をすることができます。 また、キャラ \\(i\\) が キャラ \\(j\\) に有利であるときは、必ずキャラ \\(j\\) が キャラ \\(i\\) に不利となっています。 さて、カトー君は負けず嫌いなため、シンヤ君に負けないように一部のキャラに絞って練習をすることにしました。 具体的には、ある区間 \\(\[L,R\]\\) を選択して、その区間内のキャラを練習します。 また、より有利に試合を進めるために、次の条件を満たす区間を選ぶことにしました。 - 相手がいかなるキャラを選んでも、そのキャラに対して五分、もしくは有利なキャラが少なくとも一体は存在する。ただし、相手と同じキャラはその候補から除外する。 普段は勉強で忙しいカトー君は、できるだけ練習するキャラの数を少なくしたいです。忙しいカトー君の代わりに、練習するキャラを選んであげてください。

入力は以下の形式で標準入力から与えられる。 ``` \(N\) \(M\) \(a_1\) \(b_1\) \(a_2\) \(b_2\) \(\vdots\) \(a_M\) \(b_M\) ```

問題の条件を満たす最小の区間の両端 \\(L,R\\) \\((L \\leq R)\\) をスペース区切りで出力せよ。幅が最小となる区間が複数存在する場合は、 \\(L\\) の値が最も小さいものを出力せよ。 問題の条件を満たすような区間がない場合は `-1` を出力せよ。 ``` \(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) \\) (正反対の条件が同時に入力されることはない) が成り立つ。 - 入力される値はすべて整数である。 - なお、入力で与えられなかった相性については、全て五分であることが保証される。 ### Sample Explanation 1 例えば、キャラ \\\\(1\\\\) と \\\\(3\\\\) に対してはキャラ \\\\(2\\\\) を、キャラ \\\\(2\\\\) に対してはキャラ \\\\(3\\\\) を選択することで、任意の相手キャラに対して五分以上の相性で対戦することができます。 ### Sample Explanation 2 例えば、キャラ \\\\(1\\\\) と \\\\(2\\\\) に対してはキャラ \\\\(3\\\\) を、キャラ \\\\(3\\\\) に対してはキャラ \\\\(1\\\\) を選択することで、任意の相手キャラに対して五分以上の相性で対戦することができます。 また、区間の中で、一度も選ばれないキャラが存在していても構いません。 ### Sample Explanation 3 キャラ \\\\(2\\\\) に対して五分以上の相性となるキャラは存在しません。