寻找四元环

题目描述

有一个具有 $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$ 的环称为四元环。

如果 $G$ 包含四元环,请选择其中任意一个,并输出该环上的顶点。你可以按任意顺序输出顶点。

如果 $G$ 不包含四元环,则输出 -1。

什么是独立集?

图 $G$ 的独立集是指由 $G$ 中的部分顶点组成的集合 $V'$,满足 $V'$ 中任意两个顶点之间都没有边。

输入格式

输入按以下格式从标准输入给出:

S T M
u_1 v_1
u_2 v_2
⋮
u_M v_M

输出格式

如果 $G$ 包含四元环,请选择其中任意一个,并输出该环上四个不同顶点的编号。(顶点的顺序无关。)

如果 $G$ 不包含四元环,则输出 -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$ 构成一个四元环。所以应输出 $1$、$2$、$4$、$5$。

顶点可以按任意顺序输出。除了样例输出之外,例如输出 2 5 1 4 也被认为是正确的。

3 2 4
1 4
1 5
2 5
3 5

-1

有些输入中 $G$ 可能不包含四元环。

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 \le S \le 3 \times 10^5$
• $2 \le T \le 3000$
• $4 \le M \le \min(S \times T, 3 \times 10^5)$
• $1 \le u_i \le S$
• $S + 1 \le v_i \le S + T$
• 如果 $i \neq j$,则 $(u_i, v_i) \neq (u_j, v_j)$。
• 输入中的所有值均为整数。

提示

答案不唯一,输出任意合法解即可。