AT_abc260_f [ABC260F] 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$ 都是独立集。

长度为 $4$ 的环称为 4-cycle。
如果 $G$ 包含 4-cycle，请任选一个 4-cycle，并输出该环中包含的顶点编号（顺序不限）。
如果 $G$ 不包含 4-cycle，请输出 -1。

独立集的定义：图 $G$ 的独立集是指 $G$ 中由若干顶点组成的集合 $V'$，满足 $V'$ 中任意两个顶点之间都没有边相连。

输入格式

输入按以下格式从标准输入读入。

$S$ $T$ $M$
$u_1$ $v_1$
$u_2$ $v_2$
$\vdots$
$u_M$ $v_M$

输出格式

如果 $G$ 包含 4-cycle，请任选一个 4-cycle，并输出该环中包含的 $4$ 个不同顶点的编号（顺序不限）。
如果 $G$ 不包含 4-cycle，请输出 -1。

输入输出样例 #1

输入 #1

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

输出 #1

1 2 4 5

输入输出样例 #2

输入 #2

3 2 4
1 4
1 5
2 5
3 5

输出 #2

-1

输入输出样例 #3

输入 #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

说明/提示

限制条件

• $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)$
• 输入的所有值均为整数

样例解释 1

由于顶点 $1$ 和 $4$、$4$ 和 $2$、$2$ 和 $5$、$5$ 和 $1$ 之间都有边，因此顶点 $1, 2, 4, 5$ 构成一个 4-cycle。所以输出 $1, 2, 4, 5$ 即可。顶点输出顺序不限，除了样例输出之外，例如 2 5 1 4 这样的输出也是正确答案。

样例解释 2

也存在 $G$ 不包含 4-cycle 的输入。

由 ChatGPT 4.1 翻译