22929번 - Special Cycle 스페셜 저지다국어

문제

You are given a simple undirected graph with no self-loops or multiple edges. Some of the edges are marked as Special.

Your task is to find a simple cycle where, for each Special edge, that edge either belongs to the cycle or neither of its endpoints touch the cycle. The cycle is not allowed to repeat vertices. Output any solution, or report that none exist.

입력

The first line of input contains three integers $n$ (2ドル \le n \le 150$), $m$ (1ドル \le m \le \frac{n \cdot (n-1)}{2}$) and $k$ (1ドル \le k \le m$), where $n$ is the number of nodes in the graph, $m$ is the number of edges, and $k$ is the number of edges that are Special. The nodes are numbered 1ドル$ through $n$.

Each of the next $m$ lines contains two integers $a$ and $b$ (1ドル \le a < b \le n$), denoting an undirected edge between nodes $a$ and $b$. All edges are distinct. The first $k$ edges are the Special edges.

출력

Output an integer denoting the length of the found cycle on one line. On subsequent lines, output the vertices of the cycle in order around the cycle, one per line. If no such cycle exists, simply output $-1$.

제한

힌트