Find 4-cycle

题目描述

我们有一个简单的无向图 $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$。

输入格式

输入按照标准输入，格式如下给出： $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

3 2 4
1 4
1 5
2 5
3 5

-1

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

提示

$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$ 和 $4$、$4$ 和 $2$、$2$ 和 $5$、以及 $5$ 和 $1$，因此顶点 $1$、$2$、$4$、和 $5$ 构成一个 4-环。所以应该输出 $1$、$2$、$4$、和 $5$。
顶点可以按任意顺序输出。除示例输出外，例如 $2 5 1 4$ 也被认为是正确的。
某些输入可能使得 $G$ 不包含 4-环。

标签: AtCoder|abc260F

来源

AtCoder|abc260F