EDGE (DHBB 2021 T.Thử)

View as PDF

Submit solution

Points: 200.00 (partial)
Time limit: 1.0s
Memory limit: 1G
Input: stdin
Output: stdout

Author:
Problem type
Allowed languages
C, C++, GAS64, Pascal, Perl, PHP, Python, Sed, TCL, Text

Ở 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 ≤ n ≤ 100000, 0 ≤ m ≤ 200000)~. Mỗi dòng trong ~m~ dòng tiếp theo ghi ~2~ số ~a_i~ và ~b_i (1 ≤ a_i, b_i ≤ n, a_i ≠ 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

Nguồn: 2021 Thi thử


Comments

Please read the guidelines before commenting.


There are no comments at the moment.