Gửi bài giải


Điểm: 0,20 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout

Nguồn bài:
stolen
Dạng bài
Ngôn ngữ cho phép
C++, Pascal, Python

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~.

Sample Test

Input:

4 2
1 2
1 4

Output:

2
1 2
2 4