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`。

## 限制条件 - $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 翻译