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

Xem dạng PDF
Gửi bài giải
Điểm: 0,14 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 512M
Input: stdin
Output: stdout
Nguồn bài:
Bài cổ điển - tests added by canhteo
Dạng bài
Ngôn ngữ cho phép
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

Bình luận

Hãy đọc nội quy trước khi bình luận.


  • -1
    Free_De_La_Zenith  đã bình luận lúc 18, Tháng 3, 2025, 7:37

    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


  • -7
    phanthedan2009  đã bình luận lúc 14, Tháng 2, 2025, 7:48

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • -5
    avatarstar1133  đã bình luận lúc 13, Tháng 2, 2025, 13:54

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • -40
    tandochuyentin2022  đã bình luận lúc 3, Tháng 9, 2024, 8:26

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • 12
    levanhuyluc  đã bình luận lúc 3, Tháng 9, 2024, 7:06

    Nếu bạn đã hoàn thành bài này và cảm thấy khá tốt thì hãy đến với bài khó hơn nhé: Đây là bài khó hơn: https://lqdoj.edu.vn/problem/upgrade Ở bài này các bạn phải vận dụng thêm là thuật toán Dijkstra và xây 1 đồ thị con để tối ưu Chúc các bạn thành công nhé ❤


  • -2
    nhanphamj  đã bình luận lúc 11, Tháng 7, 2024, 14:56

    xin ý tưởng mấy bro


  • -5
    KienHungg  đã bình luận lúc 6, Tháng 6, 2024, 8:37

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • 3
    BangLee  đã bình luận lúc 26, Tháng 5, 2024, 4:09 ← sửa 3

    Bạn nào mà nộp bằng Python3 hay PyPy3 rất có thể sẽ bị lỗi phần nhập input valueError nếu như nhập bình thường, nếu bạn bị lỗi có thể làm theo cách này:

    import sys

    input = sys.stdin.read

    data = input().split() #(chia nhỏ toàn bộ input và nhập vào data)

    n,m = int(data[0]),int(data[1]) #(lúc này trong data[0] và data[1] sẽ tương ứng là n và m)

    index = 2 #(đặt biến index để duyệt những phần nhập số liệu còn lại)

    for _ in range(m):

    u,v = int(data[index]), int(data[index + 1]) #nhập cạnh u,v từ dữ liệu trong data

    index += 2 # nhớ là tăng index sau mỗi lần

    Chúc các bạn k bị lỗi ValueError


    • -3
      messizutaki  đã bình luận lúc 2, Tháng 10, 2024, 6:02

      đáng yêu v tr


  • -81
    nthquan_1505  đã bình luận lúc 16, Tháng 3, 2023, 9:19

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


    • -44
      yanwe111  đã bình luận lúc 22, Tháng 3, 2023, 3:32

      Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • -81
    chubedanye  đã bình luận lúc 16, Tháng 3, 2023, 7:10

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • -47
    nthquan_1505  đã bình luận lúc 15, Tháng 3, 2023, 4:50 ← chỉnh sửa

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


    • -39
      ducdacoder3103  đã bình luận lúc 16, Tháng 3, 2023, 7:11

      Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


      • -35
        yanwe111  đã bình luận lúc 22, Tháng 3, 2023, 3:32

        Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


    • -43
      chubedanye  đã bình luận lúc 16, Tháng 3, 2023, 7:09

      Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • -23
    hoangheovn  đã bình luận lúc 13, Tháng 3, 2023, 8:55

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • 22
    21ti_hdhphat  đã bình luận lúc 13, Tháng 2, 2023, 17:07

    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


    • -37
      maintainit  đã bình luận lúc 22, Tháng 2, 2023, 12:40

      Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.