Bạn có một đồ thị vô hướng liên thông gồm ~n~ đỉnh và ~m~ cạnh, các đỉnh được đánh số từ ~1~ tới ~n~. Bạn cần phải làm một trong hai công việc sau, tùy bạn lựa chọn:

1. Tìm một tổ hợp độc lập có lực lượng chính xác ~\lceil\sqrt{n}\rceil~ phần tử (ký hiệu ~\lceil x \rceil~ với ~x > 0~ là số nguyên bé nhất ~\geq x~; ví dụ: ~\lceil 4.2 \rceil = 5~, ~\lceil 4.7 \rceil = 5~, ~\lceil 4 \rceil = 4~).
   • Một tổ hợp độc lập là một tập hợp các đỉnh của đồ thị sao cho hai đỉnh bất kỳ trong tập hợp đều không có cạnh nối giữa chúng.
2. Tìm một chu trình đơn có độ dài không ít hơn ~\lceil\sqrt{n}\rceil~ đỉnh.
   • Một chu trình đơn là một chu trình chứa mỗi đỉnh không quá một lần.

Có thể chứng minh luôn có một trong hai công việc có thể làm được, nhưng bạn có thể thử chứng minh lại, tuỳ bạn.

Yêu cầu

Bạn hãy lựa chọn một trong hai công việc trên và in ra các đỉnh thỏa tính chất đó

Dữ liệu

• Dòng đầu chứa hai số nguyên dương là ~n,m~ - số đỉnh và số cạnh của đồ thị(~5 \le n \le 2\cdot10^5~, ~n-1 \le m \le min({n(n-1)\over2},5\cdot10^5)~).
• ~m~ dòng tiếp theo chứa hai số ~u,v~ thể hiện đồ thị có cạnh giữa ~u~ và ~v~ (~1 \leq u, v \leq n~).
• Dữ liệu vào đảm bảo đồ thị liên thông, giữa hai đỉnh bất kì chỉ có tối đa một cạnh và không có cạnh nào nối một đỉnh đến chính đỉnh đó.

Kết quả

Với mỗi bộ test:

• Nếu bạn chọn công việc 1: Dòng đầu in "1". Dòng tiếp theo in ~\lceil\sqrt{n}\rceil~ số nguyên dương là các đỉnh thuộc tổ hợp độc lập được chọn.
• Nếu bạn chọn công việc 2: Dòng đầu in "2". Dòng tiếp theo in một số nguyên dương ~k~ là độ dài của chu trình đơn tìm được. Dòng cuối in ~k~ số nguyên dương là các đỉnh thuộc chu trình đó, theo thứ tự xuất hiện trong chu trình.
• Nếu có nhiều đáp án, bạn hãy xuất ra đáp án bất kỳ, tùy bạn lựa chọn.

Ví dụ

Input 1

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

Output 1

1 
2 4 7

Input 2

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

Output 2

2
4
1 6 3 2

Input 3

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

Output 3

1
6 2 7 4

Note

• Chú ý ở test ví dụ đầu, một đáp án khác có thể là

2
4
4 1 7 3