题目描述

我们有一个简单无向图 $G$，包含 $(S+T)$ 个顶点和 $M$ 条边。顶点编号为 $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环。
如果 $G$ 包含4环，选择其中任意一个并打印环中的顶点。可以以任意顺序打印顶点。
如果 $G$ 不包含4环，打印 -1。

什么是独立集？对于图 $G$ 的一个顶点集 $V'$ 而言，如果 $V'$ 中的任意两个顶点之间没有边相连，那么 $V'$ 就是图 $G$ 的一个独立集。

约束条件

• $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环，选择其中一个并打印环中四个不同顶点的索引。（顶点的顺序不重要）
如果 $G$ 不包含4环，打印 -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环。所以，应该打印 $1$、$2$、$4$ 和 $5$。
顶点的顺序可以任意。除了示例输出外，例如 2 5 1 4 也被认为是正确的。

示例输入 2

3 2 4
1 4
1 5
2 5
3 5

示例输出 2

-1

某些输入可能导致 $G$ 不包含4环。

示例输入 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