A7722 | $Odd Cycle$

时间限制2s

内存限制1024MB

通过 / 提交0/0

题目描述

给你一个包含 $N$ 个编号为 $1$ 至 $N$ 的顶点和 $M$ 条边的简单连通无向图。第 $i$ 条边连接顶点 $a_i$ 和 $b_i$。 判断图中是否存在由奇数个顶点构成的环；若存在，输出其中任意一个这样的环。 形式化地说，判断是否存在一个整数序列 $(v_1,v_2,\ldots,v_K)$，满足以下所有条件；若存在，输出其中任意一个这样的序列： * $K$ 是一个不小于 $3$ 的奇数； * $v_1,v_2,\ldots,v_K$ 互不相同； * 对每个满足 $1\le i \le K$ 的整数 $i$，顶点 $v_i$ 与 $v_{i+1}$ 之间存在一条边，其中定义 $v_{K+1} = v_1$。 你将收到 $T$ 组测试数据，请对每组数据求解。

输入从标准输入中按以下格式给出： > $T$ > $\mathrm{case}_1$ > $\mathrm{case}_2$ > $\vdots$ > $\mathrm{case}_T$ 每个测试用例按以下格式给出： > $N$ $M$ > $a_1$ $b_1$ > $a_2$ $b_2$ > $\vdots$ > $a_M$ $b_M$

对于每个测试用例，若不存在满足条件的序列，则输出 -1；否则，按以下格式输出任意一个满足条件的序列： > $K$ > $v_1$ $v_2$ $\ldots$ $v_K$

输入 #1

输出 #1

C++ 编辑器

输入

输出