Đường phố Berland

Thủ đô của Berland có $n$ nút giao thông, một số cặp nút được nối với nhau bằng đường hai chiều. Giữa mỗi cặp nút có nhiều nhất một con đường, và từ nút bất kỳ đều đi tới được mọi nút khác.

Vì kẹt xe ngày càng nghiêm trọng, ban quản lý thành phố muốn mạng lưới đạt tiêu chuẩn: giữa hai nút giao bất kỳ luôn tồn tại ít nhất hai đường đi không dùng chung con đường nào (hai đường đi đó được phép đi qua chung nút giao).

Hãy xây thêm số con đường ít nhất để tiêu chuẩn trên được thoả mãn. Mỗi con đường mới nối hai nút giao khác nhau, và sau khi xây xong mạng lưới vẫn phải giữ nguyên tính chất giữa mỗi cặp nút có nhiều nhất một con đường (nghĩa là không được xây một con đường trùng với con đường đã có, cũng không được xây hai con đường mới nối cùng một cặp nút).

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $m$: số nút giao và số con đường hiện có.
• $m$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên $a_i$, $b_i$: con đường thứ $i$ nối nút $a_i$ và nút $b_i$.

Dữ liệu ra

• Dòng đầu in ra $t$: số con đường ít nhất cần xây thêm.
• $t$ dòng tiếp theo, mỗi dòng in hai số nguyên mô tả một con đường mới. Có thể in các con đường theo thứ tự bất kỳ, và hai đầu mút của mỗi con đường cũng theo thứ tự bất kỳ.

Nếu mạng lưới đã đạt tiêu chuẩn, in ra duy nhất số $0$. Nếu không có cách xây nào thoả mãn, in ra $-1$.

Nếu có nhiều đáp án cùng số lượng nhỏ nhất, in ra đáp án bất kỳ.

Ràng buộc

• $2\le n\le 900$
• $1\le m\le 100000$
• $1\le a_i,b_i\le n$ và $a_i\ne b_i$
• Không có hai con đường nối cùng một cặp nút
• Đồ thị đã cho liên thông

Ví dụ