Chu trình trong đồ thị

Cho một đồ thị vô hướng $G$ gồm $n$ đỉnh, các đỉnh được đánh số từ $1$ đến $n$. Biết rằng mỗi đỉnh của đồ thị được nối trực tiếp bằng cạnh với ít nhất $k$ đỉnh khác.

Nhiệm vụ của bạn là tìm trong đồ thị một chu trình đơn có độ dài ít nhất $k+1$.

Một chu trình đơn độ dài $d$ (với $d>1$) là một dãy các đỉnh đôi một khác nhau $v_1,v_2,\dots ,v_d$ sao cho $v_1$ và $v_d$ được nối bằng một cạnh, đồng thời với mọi $i$ ($1\le i<d$), hai đỉnh $v_i$ và $v_{i+1}$ cũng được nối bằng một cạnh.

Dữ liệu đảm bảo luôn tồn tại đáp án. Nếu có nhiều đáp án, bạn được in ra bất kỳ đáp án nào hợp lệ.

Dữ liệu vào

• Dòng đầu chứa ba số nguyên $n$, $m$, $k$: số đỉnh, số cạnh và cận dưới của bậc mỗi đỉnh.
• $m$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $a_i$, $b_i$: chỉ số hai đỉnh được nối bởi cạnh thứ $i$.

Đồ thị không chứa cạnh bội (nhiều cạnh giữa cùng một cặp đỉnh) và không chứa khuyên (cạnh nối một đỉnh với chính nó).

Dữ liệu ra

• Dòng đầu in số nguyên $r$ ($r\ge k+1$): độ dài chu trình tìm được.
• Dòng thứ hai in $r$ số nguyên khác nhau $v_1,v_2,\dots ,v_r$: các đỉnh của chu trình theo thứ tự.

Ràng buộc

• $3\le n,m\le {10}^5$
• $2\le k\le n-1$
• $1\le a_i,b_i\le n$, $a_i\ne b_i$

Ví dụ