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 \le M~, ~N \le 1000~, ~M \le 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 \le K \le 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.

Sample Input

3 3
1 2
2 3
3 1

Sample Output

3
1 2
2 3
2 3
3 1
1 2
3 1

Note

• 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