Дан простой неориентированный граф без петель и кратных ребер. Некоторые ребра помечены как специальные (Special).

Ваша задача — найти простой цикл такой, что для каждого специального ребра это ребро либо принадлежит циклу, либо ни одна из его вершин не входит в цикл. Цикл не должен содержать повторяющихся вершин. Выведите любое решение или сообщите, что его не существует.

Входные данные

Первая строка входных данных содержит три целых числа $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$.

Примеры

Входные данные 1

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

Выходные данные 1

8
1
4
5
6
7
8
3
2

Входные данные 2

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

Выходные данные 2

-1