题目描述

$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 を出力せよ。

题目大意

给定一个二分图，其左部点的个数为 $S$，右部点的个数为 $T$，边数为 $M$，请找出一个四元环，任意顺序输出这 $4$ 个节点，如果不存在则输出 $-1$。

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

1 2 4 5

3 2 4
1 4
1 5
2 5
3 5

-1

4 5 9
3 5
1 8
3 7
1 9
4 6
2 7
4 8
1 7
2 9

1 7 2 9

提示

制約

• $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 を含まない入力もあります。