Cho một đơn đồ thị liên thông gồm N đỉnh, M cạnh. Các đỉnh của đồ thị được đánh số từ 1 đến N. Tìm 3 cây khung khác nhau của đồ thị.

Định nghĩa cây khung của đồ thị:

Cây khung của đồ thị G gồm N đỉnh, M cạnh, là một đồ thị G’ gồm tất cả N đỉnh của đồ thị G, và đúng N-1 cạnh của đồ thị G, và G’ là đồ thị liên thông.

Input

• Dòng đầu: 2 số nguyên dương N và M (1 < N <= M, N <= 1000, M <= 1500)
• M dòng tiếp theo, mỗi dòng gồm 2 số nguyên dương u, v (u khác v) thể hiện 1 cạnh nối giữa u và v. Input đảm bảo đồ thị liên thông và có ít nhất 3 cây khung khác nhau.

Output

• Dòng 1 gồm 1 số nguyên dương K duy nhất - số cây khung mà bạn tìm được (0 <= K <= 3).
• Tiếp theo là K nhóm dòng, mỗi nhóm dòng gồm đúng N-1 dòng, thể hiện 1 cây khung.

Cách tính điểm

• Nếu trong K cây khung mà bạn tìm được, có một cây khung không hợp lệ (có chu trình, không liên thông), hoặc có 2 cây khung giống nhau thì bạn không được điểm nào
• Nếu K = 0, bạn không được điểm nào
• Nếu K = 1, bạn được 20% số điểm của test
• Nếu K = 2, bạn được 40% số điểm của test
• Nếu K = 3, bạn được 100% số điểm của test

Bài này có đúng 20 test, tổng điểm là 100. Trong lúc thi bạn chỉ được chấm với 2 test (không bao gồm test đề bài), và điểm tối đa mà bạn có thể nhận được là 10 điểm.

Example

Input
3 3
1 2
2 3
3 1

Output
3
1 2
2 3
2 3
3 1
3 1
1 2