Dany jest prosty graf nieskierowany bez pętli własnych i krawędzi wielokrotnych. Niektóre krawędzie są oznaczone jako specjalne (ang. Special).

Twoim zadaniem jest znalezienie cyklu prostego, w którym dla każdej krawędzi specjalnej zachodzi warunek: krawędź ta albo należy do cyklu, albo żaden z jej końców nie należy do cyklu. Cykl nie może powtarzać wierzchołków. Wypisz dowolne rozwiązanie lub poinformuj, że takie nie istnieje.

Wejście

Pierwsza linia wejścia zawiera trzy liczby całkowite $n$ ($2 \le n \le 150$), $m$ ($1 \le m \le \frac{n(n-1)}{2}$) oraz $k$ ($1 \le k \le m$), gdzie $n$ to liczba wierzchołków w grafie, $m$ to liczba krawędzi, a $k$ to liczba krawędzi specjalnych. Wierzchołki są ponumerowane od $1$ do $n$.

Każda z kolejnych $m$ linii zawiera dwie liczby całkowite $a$ i $b$ ($1 \le a < b \le n$), oznaczające krawędź nieskierowaną między wierzchołkami $a$ i $b$. Wszystkie krawędzie są różne. Pierwsze $k$ krawędzi to krawędzie specjalne.

Wyjście

Wypisz w jednej linii liczbę całkowitą oznaczającą długość znalezionego cyklu. W kolejnych liniach wypisz wierzchołki cyklu w kolejności ich występowania, po jednym w linii. Jeśli taki cykl nie istnieje, wypisz $-1$.

Przykład

Wejście 1

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

Wyjście 1

8
1
4
5
6
7
8
3
2

Wejście 2

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

Wyjście 2

-1