HỆ THỐNG XE BUS

Xem PDF

Điểm: 200 (p) Thời gian: 1.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Hệ thống xe bus của thành phố nơi cậu sinh viên \(Z\) đang ở là một đồ thị vô hướng gồm có \(N\) trạm và \(M\) tuyển đường.

Thành phố của cậu đang có kế hoạch bỏ đi một trạm và tuyến đường đã cũ và xây mới trong tương lại. Là một người thường xuyên sử dụng các phương tiện công cộng như xe bus để bảo vệ môi trường, \(Z\) nhận thấy một số trạm và tuyến đường khi nó bị gỡ bỏ sẽ lập tức ảnh hưởng tới việc đi lại.

Hãy giúp \(Z\) đếm số trạm và số tuyến đường nếu bị gỡ bỏ sẽ có thể làm một vài cặp trạm không thể đi lại được như trước, một cặp trạm được gọi là không thể đi lại được như trước nếu như trước khi gỡ bỏ từ \(u\) có thể đi được với \(v\) nhưng sau khi bỏ đi một trạm hoặc tuyển đường nào đó thì \(u\) không thể đi được tới \(v\) nữa.

Input

  • Dòng đầu tiên gồm hai số \(N\)\(M\) (\(1 \le n \le 10000, 1 \le m \le 50000\)) lần lượt là số trạm và số tuyến đường.

  • \(M\) dòng tiếp theo, mỗi dòng gồm \(2\) số \(u\)\(v\) (\(1 \le u, v \le n\)) là hai trạm xe bus có đường đi trực tiếp tới nhau

Output

  • Gồm hai số lần lượt là số trạm và số tuyến đường nếu bỏ sẽ ngay lập tức gây ảnh hưởng tới việc đi lại.

Example

Test 1

Input
10 12 
1 10 
10 2
10 3
2 4
4 5
5 2
3 6
6 7
7 3
7 8
8 9
9 7
Output
4 3
Note

Các trạm có thể gây ảnh hưởng khi bị bỏ là: \(2\) \(3\) \(7\) \(10\)
Các tuyến đường có thể gây ảnh hưởng khi bị bỏ là: \(2\) \(10,\) \(3\) \(10,\) \(1\) \(10\)


Bình luận


  • 2
    minhtuanitk20    11:32 p.m. 25 Tháng 1, 2022

    bài này thực chất chỉ là bài đếm khớp cầu