Thi thử Duyên hải 2021 - Lần 1 - Bài 2 - EDGE

Xem dạng PDF

Gửi bài giải


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

Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Ở một số quốc gia có ~n~ thành phố và ~m~ con đường giữa chúng. Hệ thống đường bộ được tổ chức như sau:

  • Giữa hai thành phố không quá một con đường;
  • Không có con đường kết nối thành phố với chính nó.

Chính phủ quyết định thực hiện cải cách hệ thống đường sá như sau:

  • Phá hủy một trong những con đường hiện có;
  • Xây dựng một con đường mới không có trước đó, con đường này không dẫn từ thành phố đến chính nó.

Ngoài ra, để cải thiện mối quan hệ kinh tế giữa các thành phố, chính phủ muốn sau khi cải cách, có thể đi đường bộ giữa bất kỳ 2 thành phố nào. Không đảm bảo rằng yêu cầu này được đáp ứng trước khi cải cách.

Hãy giúp chính phủ xác định xem có bao nhiêu cách cải cách.

Input

Dòng đầu tiên ghi ~2~ số nguyên ~n~ và ~m~ ~(1 \leq n \leq 100000~, ~0 \leq m \leq 200000)~.

Mỗi dòng trong ~m~ dòng tiếp theo ghi ~2~ số ~a_i~ và ~b_i~ ~(1 \leq a_i~, ~b_i~ ~\leq n~, ~a_i \neq b_i)~ - số thứ tự ~2~ thành phố đầu mút của con đường thứ ~i~.

Output

In ra số cách cải cách

Sample Input

4 4
1 2
2 3
1 3
3 4

Sample Output

8

Note

Đề gốc thi thử duyên hải 2021 lần 1


Bình luận

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



  • 6
    phamdinhtuananh  đã bình luận lúc 10, Tháng 3, 2024, 5:09 chỉnh sửa

    Bài tương tự ạ https://oj.vnoi.info/problem/reform


  • -22
    NEIK  đã bình luận lúc 4, Tháng 5, 2021, 10:00

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


    • 10
      ngkan  đã bình luận lúc 4, Tháng 5, 2021, 10:59

      Có nút đọc lời giải ở dưới phần nộp bài đấy bạn