Nitori Kawashiro cần thiết kế hệ thống cáp treo 2 chiều giữa \(n\) địa điểm. Biết rằng nếu có đường đi giữa địa điểm \(a\) tới địa điểm \(b\) và từ địa điểm \(b\) tới địa điểm \(c\) thì có thể đi từ \(a\) đến \(c\). Hãy cho biết cần xây dựng ít nhất bao nhiêu đường đi trực tiếp giữa 2 địa điểm để kết nối \(m\) cặp địa điểm cho trước.

Nói tóm lại, từ đồ thị được cho ban đầu, hãy tìm cách giữ lại ít cạnh nhất sao cho số vùng liên thông được giữ nguyên.

Input

• Dòng đầu tiên gồm 2 số tự nhiên \(n, m \le 10^5\).
• \(m\) dòng tiếp theo mỗi dòng gồm 2 địa điểm \(u, v \le n\).

Output

• In ra một số \(p\) là số lượng đường đi trực tiếp giữa 2 địa điểm.
• \(p\) dòng sau mỗi dòng in ra 2 số \(u, v\) nghĩa là xây đường đi giữa 2 địa điểm \(u\) và \(v\).
• Nếu có nhiều đáp án thỏa mãn, bạn có thể in ra đáp án bất kì.

Example

4 2
1 2
1 4

2
1 2
2 4

4 3
1 2
2 3
3 1

2
1 2
1 3