分数: 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