F - Find 4-cycle /

### 問題文

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 はともに独立集合です。

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

### 入力例 1

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


### 出力例 1

1 2 4 5


### 入力例 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