Tìm khớp và cầu (Cơ bản)

View as PDF

Submit solution


Points: 0.14 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
Bài cổ điển - tests added by canhteo
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Xét đơn đồ thị vô hướng ~G =~ ~(V~, ~E)~ có ~N~ ~(1 \le N \le 10000)~ đỉnh và ~M~ ~(1 \le M \le 50000)~ cạnh. Người ta định nghĩa một đỉnh gọi là khớp nếu như xoá đỉnh đó sẽ làm tăng số thành phần liên thông của đồ thị. Tương tự như vậy, một cạnh được gọi là cầu nếu xoá cạnh đó sẽ làm tăng số thành phần liên thông của đồ thị.

Vấn đề đặt ra là cần phải đếm tất cả các khớp và cầu của đồ thị ~G~.

Input

  • Dòng đầu: chứa hai số tự nhiên ~N~, ~M~.
  • ~M~ dòng sau mỗi dòng chứa một cặp số ~(u~, ~v)~ ~(u~ khác ~v~, ~1 \le u \le N~, ~1 \le v < N)~ mô tả một cạnh của ~G~.

Output

  • Gồm một dòng duy nhất ghi hai số, số thứ nhất là số khớp, số thứ hai là số cầu của ~G~

Sample 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

Sample Output

4 3

Note

image


Comments

Please read the guidelines before commenting.



  • -42
    nthquan_1505  commented on March 16, 2023, 9:19 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


    • -21
      yanwe111  commented on March 22, 2023, 3:32 a.m.

      This comment is hidden due to too much negative feedback. Show it anyway.


  • -43
    chubedanye  commented on March 16, 2023, 7:10 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -30
    nthquan_1505  commented on March 15, 2023, 4:50 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


    • -24
      ducdacoder3103  commented on March 16, 2023, 7:11 a.m.

      This comment is hidden due to too much negative feedback. Show it anyway.


      • -21
        yanwe111  commented on March 22, 2023, 3:32 a.m.

        This comment is hidden due to too much negative feedback. Show it anyway.


    • -26
      chubedanye  commented on March 16, 2023, 7:09 a.m.

      This comment is hidden due to too much negative feedback. Show it anyway.


  • -13
    hoangheovn  commented on March 13, 2023, 8:55 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • 10
    21ti_hdhphat  commented on Feb. 13, 2023, 5:07 p.m.

    Nếu bạn bị dính WA 2 test cuối và muốn biết lí do tại sao sai:

    Input có thể cho một đồ thị không liên thông


    • -22
      maintainit  commented on Feb. 22, 2023, 12:40 p.m.

      This comment is hidden due to too much negative feedback. Show it anyway.