Ehab's Last Corollary

Cho một đồ thị vô hướng liên thông gồm $n$ đỉnh và một số nguyên $k$. Bạn cần thực hiện một trong hai việc sau:

• Tìm một tập độc lập gồm đúng $\lceil k/2\rceil$ đỉnh, hoặc
• Tìm một chu trình đơn có độ dài không vượt quá $k$.

Tập độc lập là một tập đỉnh sao cho không có hai đỉnh nào trong tập được nối bởi một cạnh. Chu trình đơn là một chu trình không đi qua đỉnh nào quá một lần.

Có thể chứng minh rằng với mọi dữ liệu vào, luôn giải được ít nhất một trong hai việc trên. Nếu cả hai đều thực hiện được, bạn chỉ cần in ra một trong hai.

Dữ liệu vào

• Dòng đầu chứa ba số nguyên $n$, $m$ và $k$: số đỉnh, số cạnh của đồ thị, và tham số $k$.
• $m$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u$ và $v$ cho biết có một cạnh nối hai đỉnh $u$ và $v$.

Đồ thị liên thông, không chứa khuyên và không chứa cạnh bội.

Dữ liệu ra

Nếu bạn chọn giải việc thứ nhất: in ra $1$ trên dòng đầu, sau đó là một dòng chứa $\lceil k/2\rceil$ số nguyên phân biệt không vượt quá $n$ là các đỉnh của tập độc lập.

Nếu bạn chọn giải việc thứ hai: in ra $2$ trên dòng đầu, sau đó là một dòng chứa một số nguyên $c$ là độ dài chu trình tìm được, và một dòng chứa $c$ số nguyên phân biệt không vượt quá $n$ là các đỉnh của chu trình theo thứ tự xuất hiện trên chu trình.

Nếu có nhiều đáp án đúng, in ra bất kỳ đáp án nào.

Ràng buộc

• $3\le k\le n\le {10}^5$
• $n-1\le m\le 2·{10}^5$
• $1\le u,v\le n$

Ví dụ