Танд $n$ ширхэг оройноос бүтсэн чиглэлгүй $G$ граф байна. Бид графын оройнуудыг $1$-ээс $n$ хүртэл дугаарлагдсан гэж үзнэ. Бидний мэдэж байгаагаар $G$ графын орой бүр нь өөрөөсөө бусад дор хаяж $k$ ширхэг оройтой ирмэгээр холбогдсон. Таны даалгавар бол өгөгдсөн графаас хамгийн багадаа $k + 1$ урттай энгийн циклийг олох юм.

$G$ граф дахь $d$ $(d > 1)$ урттай энгийн цикл гэдэг нь графын $v_{1}$ ба $v_{d}$ оройнууд ирмэгээр холбогдсон, мөн ямар нэг бүхэл $i$ $(1 ≤ i < d)$ тооны хувьд $v_{i}$ ба $v_{i + 1}$ оройнууд ирмэгээр холбогдсон байх $v_{1}, v_{2}, ..., v_{d}$ ялгаатай оройнуудын дараалал юм.

Оролт

Оролтын эхний мөрөнд $n$, $m$, $k$ $(3 ≤ n, m ≤ 10^{5}; 2 ≤ k ≤ n - 1)$ гурван бүхэл тоо байна. Эдгээр нь графын оройн тоо, ирмэгийн тоо, болон оройнуудын зэргийн хязгаар юм. Дараагийн $m$ мөрөнд хос бүхэл тоонууд байна. $i$-р мөрөнд $a_{i}$, $b_{i}$ $(1 ≤ a_{i}, b_{i} ≤ n; a_{i} ≠ b_{i})$ бүхэл тоонууд байх ба эдгээр оройнууд $i$-р ирмэгээр холбогдсон гэсэн үг.

Өгөгдсөн граф ямар нэг гогцоо агуулаагүй байна. Графын орой бүр нь дор хаяж өөрөөсөө бусад $k$ ширхэг оройтой ирмэгээр холбогдсон байна.

Гаралт

Эхний мөрөнд $r$ $(r ≥ k + 1)$ бүхэл тоог хэвлэнэ. Энэ нь олдсон циклийн урт юм. Дараагийн мөрөнд олдсон цикл болох $r$ ширхэг $v_{1}, v_{2}, ..., v_{r}$ $(1 ≤ v_{i} ≤ n)$ бүхэл тоонуудыг хэвлэнэ.

Заавал хариулттай байна. Олон хариутай тохиолдолд аль нэгийг нь хэвлэнэ.