Hình ảnh tạo bởi ChatGPT

Lần đầu được lên thành phố nên khi nhìn thấy các cây cầu, Arino rất tò mò và hứng thú. Thành phố có tổng cộng ~n~ thị trấn và ~m~ cây cầu nối giữa hai thị trấn. Thành phố hiện tại đang được kết nối, nghĩa là xuất phát từ một thị trấn bất kỳ đều có thể đến được các thị trấn còn lại.

Arino biết được rằng trong thành phố đang có lệnh giới nghiêm, những cây cầu hoặc thị trấn nào bị phong toả sẽ không thể di chuyển qua đó được. Arino đặt ra câu hỏi rằng có bao nhiêu cây cầu mà khi phong tỏa nó đồng thời phong tỏa cả hai thị trấn được nối với nó, thành phố với ~n-2~ thị trấn còn lại không còn kết nối được nữa, nghĩa là tồn tại hai thị trấn không có đường đi.

Input

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~m~ ~(4 \le n \le 10^5; n-1 \le m \le 3.10^5)~ là số lượng thị trấn và số lượng cây cầu nối.
• ~m~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~u_i~ và ~v_i~ mô tả cây cầu nối hai thị trấn ~u_i~ và ~v_i~ ~(1 \le u_i,v_i \le n; u_i \neq v_i)~.
• Dữ liệu đảm bảo giữa hai thị trấn bất kỳ đều có đường đi, ngoài ra giữa hai thị trấn bất kỳ có tối đa một cây cầu.

Output

• In ra số lượng cây cầu thỏa mãn rằng khi phong tỏa nó đồng thời phong tỏa cả hai thị trấn được nối với nó, thành phố không còn được kết nối.

Samples

Sample Input 1

4 5
1 2
2 3
3 4
4 1
1 3

Sample Output 1

1

Sample Input 2

6 7
1 2
2 4
2 6
3 5
6 1
4 3
2 5

Sample Output 2

4

Scoring

• Subtask ~1~ với ~13\%~ số điểm: ~n \le 100; m \le 300~
• Subtask ~2~ với ~17\%~ số điểm: ~n \le 1000; m \le 3000~
• Subtask ~3~ với ~25\%~ số điểm: ~n \le 1000~
• Subtask ~4~ với ~12\%~ số điểm: ~m-n \le 20~
• Subtask ~5~ với ~43\%~ số điểm: Không có ràng buộc gì thêm

Clarification

• Trong ví dụ đầu tiên, nếu phong tỏa cây cầu nối hai thị trấn thứ ~1~ và thứ ~3~, thành phố sẽ mất kết nối giữa hai thị trấn thứ ~2~ và ~4~.
• Trong ví dụ thứ hai, các cây cầu thỏa mãn bao gồm: ~(1, 2), (2, 4), (2, 6), (2, 5)~.