Xây dựng đường

Có $N$ thành phố được đánh số từ $1$ đến $N$. Ban đầu chưa có con đường nào. Nhà vua muốn xây một số con đường (mỗi con đường nối hai thành phố khác nhau, đi được theo cả hai chiều) sao cho từ mỗi thành phố có thể tới bất kỳ thành phố nào khác bằng cách đi qua không quá $2$ con đường.

Ngoài ra, có $M$ cặp thành phố mà giữa chúng không được phép xây đường trực tiếp.

Nhiệm vụ của bạn: xây số con đường ít nhất thỏa mãn các điều kiện trên. Đầu vào đảm bảo luôn tồn tại phương án hợp lệ.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $N$ và $M$.
• $M$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $a_i$ và $b_i$, cho biết không được xây đường trực tiếp giữa thành phố $a_i$ và $b_i$.

Mỗi cặp thành phố xuất hiện tối đa một lần trong danh sách cấm.

Dữ liệu ra

• Dòng đầu in ra số nguyên $s$ — số con đường tối thiểu cần xây.
• $s$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u$ và $v$ ($1\le u,v\le N$, $u\ne v$) — mô tả một con đường được xây.

Nếu có nhiều đáp án cùng đạt số con đường tối thiểu, in ra bất kỳ đáp án nào.

Ràng buộc

• $1\le N\le 1000$
• $0\le M\le 1000$
• $1\le a_i,b_i\le N$, $a_i\ne b_i$

Ví dụ