题目描述

给定一个简单无向图，图中没有自环和重边。其中部分边被标记为 特殊边。

你的任务是找到一个简单环，使得对于每一条 特殊边，该边要么属于这个环，要么它的两个端点都不与环相连（即环不包含该边的任一端点）。环不允许重复经过顶点。输出任意一个满足条件的环，若不存在则报告无解。

输入格式

输入的第一行包含三个整数 $n$（$2 \le n \le 150$）、$m$（$1 \le m \le \frac{n(n-1)}{2}$）和 $k$（$1 \le k \le m$），其中 $n$ 是图中的节点数，$m$ 是边数，$k$ 是被标记为 特殊边 的边的数量。节点的编号为 $1$ 到 $n$。

接下来的 $m$ 行，每行包含两个整数 $a$ 和 $b$（$1 \le a < b \le n$），表示节点 $a$ 与 $b$ 之间的一条无向边。所有边互不相同。前 $k$ 条边即为 特殊边。

输出格式

第一行输出一个整数，表示找到的环的长度。随后若干行，按环上的顺序依次输出环上的顶点，每行一个顶点。如果不存在这样的环，则直接输出 $-1$。

8 10 3
1 2
4 5
7 8
2 3
3 4
1 4
5 6
6 7
5 8
3 8

8
1
4
5
6
7
8
3
2

4 6 3
1 2
1 3
1 4
2 3
3 4
2 4

-1

提示

翻译由 DeepSeek V3.2 完成