配点 : $500$ 点

問題文

$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 を出力してください。

制約

• $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)$
• 入力される値はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

$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 3 5
1 3
1 4
1 5
2 4
2 5

1 2 4 5

頂点 $1$ と $4$ 、$4$ と $2$、$2$ と $5$、$5$ と $1$ の間に辺があるので 頂点 $1,2,4,5$ は 4-cycle をなします。よって $1, 2, 4, 5$ を出力すればよいです。 頂点を出力する順番は自由で、出力例のほかにも例えば 2 5 1 4 のような出力も正答となります。

3 2 4
1 4
1 5
2 5
3 5

-1

$G$ が 4-cycle を含まない入力もあります。

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