Giải bài trực tuyến

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