On vous donne un graphe simple non orienté sans boucles ni arêtes multiples. Certaines arêtes sont marquées comme étant spéciales (Special).

Votre tâche est de trouver un cycle simple tel que, pour chaque arête spéciale, cette arête appartienne au cycle ou qu'aucun de ses deux sommets ne touche le cycle. Le cycle ne doit pas répéter de sommets. Affichez n'importe quelle solution, ou indiquez qu'il n'en existe aucune.

Entrée

La première ligne de l'entrée contient trois entiers $n$ ($2 \le n \le 150$), $m$ ($1 \le m \le \frac{n(n-1)}{2}$) et $k$ ($1 \le k \le m$), où $n$ est le nombre de sommets du graphe, $m$ est le nombre d'arêtes, et $k$ est le nombre d'arêtes spéciales. Les sommets sont numérotés de $1$ à $n$.

Chacune des $m$ lignes suivantes contient deux entiers $a$ et $b$ ($1 \le a < b \le n$), désignant une arête non orientée entre les sommets $a$ et $b$. Toutes les arêtes sont distinctes. Les $k$ premières arêtes sont les arêtes spéciales.

Sortie

Affichez un entier indiquant la longueur du cycle trouvé sur une ligne. Sur les lignes suivantes, affichez les sommets du cycle dans l'ordre de parcours du cycle, un par ligne. Si aucun cycle de ce type n'existe, affichez simplement $-1$.

Exemples

Entrée 1

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

Sortie 1

8
1
4
5
6
7
8
3
2

Entrée 2

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

Sortie 2

-1