AT_abc260_f [ABC260F] Find 4-cycle

[problemUrl]: https://atcoder.jp/contests/abc260/tasks/abc260_f $ S+T $ 頂点 $ M $ 辺の単純無向グラフ $ G $ があります。頂点には $ 1 $ から $ S+T $ の番号が、辺には $ 1 $ から $ M $ の番号が割り振られています。辺 $ i $ は頂点 $ u_i $ と頂点 $ v_i $ を結んでいます。 また、頂点集合 $ V_1\ =\ \lbrace\ 1,\ 2,\dots,\ S\rbrace $ および $ V_2\ =\ \lbrace\ S+1,\ S+2,\ \dots,\ S+T\ \rbrace $ はともに独立集合です。 長さ $ 4 $ のサイクルを 4-cycle と呼びます。 $ G $ が 4-cycle を含む場合、4-cycle をどれか 1 つ選び、選んだサイクルに含まれる頂点を出力してください。頂点を出力する順番は自由です。 $ G $ が 4-cycle を含まない場合、 `-1` を出力してください。 独立集合とは？ グラフ $ G $ の独立集合とは、$ G $ に含まれるいくつかの頂点からなる集合 $ V' $ であって、$ V' $ に含まれる任意の $ 2 $ つの頂点の間に辺がないものを言います。

入力は以下の形式で標準入力から与えられる。 > $ S $ $ T $ $ M $ $ u_1 $ $ v_1 $ $ u_2 $ $ v_2 $ $ \vdots $ $ u_M $ $ v_M $

$ G $ が 4-cycle を含む場合は、任意の 4-cycle を 1 つ選び、選んだサイクルに含まれている相異なる $ 4 $ 個の頂点の番号を出力せよ。(頂点の順番は問わない。) $ G $ が 4-cycle を含まない場合は `-1` を出力せよ。

### 制約 - $ 2\ \leq\ S\ \leq\ 3\ \times\ 10^5 $ - $ 2\ \leq\ T\ \leq\ 3000 $ - $ 4\ \leq\ M\ \leq\ \min(S\ \times\ T,3\ \times\ 10^5) $ - $ 1\ \leq\ u_i\ \leq\ S $ - $ S\ +\ 1\ \leq\ v_i\ \leq\ S\ +\ T $ - $ i\ \neq\ j $ ならば $ (u_i,\ v_i)\ \neq\ (u_j,\ v_j) $ - 入力される値はすべて整数 ### Sample Explanation 1 頂点 $ 1 $ と $ 4 $ 、$ 4 $ と $ 2 $、$ 2 $ と $ 5 $、$ 5 $ と $ 1 $ の間に辺があるので 頂点 $ 1,2,4,5 $ は 4-cycle をなします。よって $ 1,\ 2,\ 4,\ 5 $ を出力すればよいです。 頂点を出力する順番は自由で、出力例のほかにも例えば `2 5 1 4` のような出力も正答となります。 ### Sample Explanation 2 $ G $ が 4-cycle を含まない入力もあります。