F - Find 4-cycle Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

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

独立集合とは？ グラフ G の独立集合とは、G に含まれるいくつかの頂点からなる集合 V' であって、V' に含まれる任意の 2 つの頂点の間に辺がないものを言います。

制約

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

入力例 1

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

出力例 1

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 のような出力も正答となります。

入力例 2

3 2 4
1 4
1 5
2 5
3 5

出力例 2

-1

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

入力例 3

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

出力例 3

1 7 2 9

Score : 500 points

Problem Statement

We have a simple undirected graph G with (S+T) vertices and M edges. The vertices are numbered 1 through (S+T), and the edges are numbered 1 through M. Edge i connects Vertices u_i and v_i.
Here, vertex sets V_1 = \lbrace 1, 2,\dots, S\rbrace and V_2 = \lbrace S+1, S+2, \dots, S+T \rbrace are both independent sets.

A cycle of length 4 is called a 4-cycle.
If G contains a 4-cycle, choose any of them and print the vertices in the cycle. You may print the vertices in any order.
If G does not contain a 4-cycle, print -1.

What is an independent set? An independent set of a graph G is a set V' of some of the vertices in G such that no two vertices of V' have an edge between them.

Constraints

  • 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
  • If i \neq j, then (u_i, v_i) \neq (u_j, v_j).
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

S T M
u_1 v_1
u_2 v_2
\vdots
u_M v_M

Output

If G contains a 4-cycle, choose any of them, and print the indices of the four distinct vertices in the cycle. (The order of the vertices does not matter.)
If G does not contain a 4-cycle, print -1.

Sample Input 1

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

Sample Output 1

1 2 4 5

There are edges between Vertices 1 and 4, 4 and 2, 2 and 5, and 5 and 1, so Vertices 1, 2, 4, and 5 form a 4-cycle. Thus, 1, 2, 4, and 5 should be printed.
The vertices may be printed in any order. Besides the Sample Output, 2 5 1 4 is also considered correct, for example.

Sample Input 2

3 2 4
1 4
1 5
2 5
3 5

Sample Output 2

-1

Some inputs may give G without a 4-cycle.

Sample Input 3

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

Sample Output 3

1 7 2 9