A7722. Odd Cycle
编程题
入门
知识点
题目描述
给你一个包含 $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$ 组测试数据，请对每组数据求解。
判断图中是否存在由奇数个顶点构成的环；若存在，输出其中任意一个这样的环。
形式化地说，判断是否存在一个整数序列 $(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$
> $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$
输出格式
对于每个测试用例，若不存在满足条件的序列，则输出
> $K$
> $v_1$ $v_2$ $\ldots$ $v_K$
-1；否则，按以下格式输出任意一个满足条件的序列：> $K$
> $v_1$ $v_2$ $\ldots$ $v_K$
输入输出样例
输入 #1
4 3 3 1 2 2 3 1 3 7 7 1 2 2 3 3 4 1 4 4 5 5 6 6 7 5 5 1 2 2 3 3 4 4 5 1 5 9 10 1 2 2 3 3 4 4 5 1 5 6 7 7 8 8 9 6 9 1 6
输出 #1
3 2 1 3 -1 5 3 2 1 5 4 5 3 2 1 5 4
说明/提示
**样例 1 解释：**
在第一个测试用例中，序列 $(2,1,3)$ 满足条件：边 $(2, 1), (1, 3), (3, 2)$ 均存在。形如 $v = (2, 3, 1)$ 的输出同样被接受。
在第二个测试用例中，图中不存在顶点数为奇数的环，因此没有序列满足条件。
### 约束条件
* $1 \le T \le 2\times10^5$
* $1 \le N, M \le 2\times10^5$
* 所有测试用例中 $N$ 的总和不超过 $2\times10^5$。
* 所有测试用例中 $M$ 的总和不超过 $2\times10^5$。
* $1 \le a_i,b_i \le N$
* $a_i\ne b_i$
* 给定图是一个简单连通无向图。
* 所有输入值均为整数。
在第一个测试用例中，序列 $(2,1,3)$ 满足条件：边 $(2, 1), (1, 3), (3, 2)$ 均存在。形如 $v = (2, 3, 1)$ 的输出同样被接受。
在第二个测试用例中，图中不存在顶点数为奇数的环，因此没有序列满足条件。
### 约束条件
* $1 \le T \le 2\times10^5$
* $1 \le N, M \le 2\times10^5$
* 所有测试用例中 $N$ 的总和不超过 $2\times10^5$。
* 所有测试用例中 $M$ 的总和不超过 $2\times10^5$。
* $1 \le a_i,b_i \le N$
* $a_i\ne b_i$
* 给定图是一个简单连通无向图。
* 所有输入值均为整数。