← 返回题目列表

AtCoder · abc260_f

I. 查找 4 周期

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

我们有一个简单的无向图 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周期。
If G 包含4个循环,选择其中任意一个并打印循环中的顶点。 您可以按任何顺序打印顶点。
If G 不包含4循环,打印 -1.

什么是独立集? 一组独立的图 G 是一套 V' 中的一些顶点 G 这样没有两个顶点 V' 之间有一条边。

约束

  • 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
  • If 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

输出

If G 包含一个 4 循环,选择其中任意一个,并打印循环中四个不同顶点的索引。 (顶点的顺序并不重要。)
If G 不包含4循环,打印 -1.


示例输入 1

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

示例输出 1

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 也被认为是正确的。


示例输入 2

3 2 4
1 4
1 5
2 5
3 5

示例输出 2

-1

一些输入可能会给出 G 没有4个周期。


示例输入 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