当前没有测试数据。

F - 寻找4环

分数：$500$ 分

问题描述

我们有一个包含 $(S+T)$ 个顶点和 $M$ 条边的简单无向图 $G$。顶点从 $1$ 到 $(S+T)$ 编号，边从 $1$ 到 $M$ 编号。边 $i$ 连接了顶点 $u_i$ 和 $v_i$。
这里，顶点集 $V_1 = \{1, 2,\dots, S\}$ 和 $V_2 = \{S+1, S+2, \dots, S+T \}$ 都是独立集。

长度为 $4$ 的环被称为4环。
如果 $G$ 包含4环，则选择其中的一个并输出环中的顶点。你可以以任何顺序输出顶点。
如果 $G$ 不包含4环，则输出 -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环，则选择其中的一个，并输出组成环的四个不同顶点的索引。（顶点的顺序无关紧要。）
如果 $G$ 不包含4环，则输出 -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环。因此，应该输出 $1$，$2$，$4$ 和 $5$。
顶点的顺序可以任意打印。例如，除了示例输出，2 5 1 4 也被视为正确的答案。

3 2 4
1 4
1 5
2 5
3 5

-1

有些输入情况下，$G$ 不包含4环。

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