Hide

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.

Input

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

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$.

Sample Input 1 Sample Output 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
Sample Input 2 Sample Output 2
4 6 3
1 2
1 3
1 4
2 3
3 4
2 4
-1
CPU Time limit 7 seconds
Memory limit 2048 MB
Statistics Show
Author
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in