trang chủ / đề bài / icpc19_nat_j

Vừa đủ cầu

Đề bài

Mô tả

Kiến Chimera là một loài thông minh và chăm chỉ.

Có một đàn gồm n con Kiến Chimera sống gần sông Hàn ở Đà Nẵng, Việt Nam. Chúng đã xây n ngôi nhà (mỗi con kiến một nhà) ở một bên bờ sông Hàn, và n bãi kiếm ăn ở bờ bên kia. Các ngôi nhà được đánh số từ 1 đến n, các bãi kiếm ăn cũng được đánh số từ 1 đến n.

Đàn kiến cũng đã xây m cây cầu bắc qua sông Hàn (m≥n), mỗi cây cầu nối một ngôi nhà với một bãi kiếm ăn. Có thể có nhiều hơn một cây cầu nối cùng một ngôi nhà với cùng một bãi kiếm ăn.

Mỗi sáng, n con kiến chọn n cây cầu để đi từ nhà của mình tới các bãi kiếm ăn.

Các cây cầu được xây sao cho đàn kiến có thể đi thẳng tới cả n bãi kiếm ăn. Nói cách khác, tồn tại một hoán vị P của các số nguyên từ 1 đến n sao cho với mọi i, có một cây cầu nối ngôi nhà thứ i với bãi kiếm ăn thứ Pi.

Đàn kiến cảm thấy chúng đã xây quá nhiều cầu. Vì vậy chúng muốn dỡ bỏ đúng một cây cầu sao cho điều kiện trên vẫn được thỏa mãn.

Dù rất thông minh, Kiến Chimera lại không giỏi tính toán. Hãy giúp đàn kiến đếm xem có bao nhiêu cây cầu khác nhau có thể dỡ bỏ.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên n và m (1≤n≤m≤105).

Mỗi dòng trong m dòng tiếp theo chứa hai số nguyên u và v (1≤u,v≤n): có một cây cầu nối ngôi nhà thứ u với bãi kiếm ăn thứ v.

Dữ liệu đảm bảo tồn tại hoán vị P như mô tả ở trên.

Dữ liệu ra

In ra số cây cầu thỏa mãn điều kiện.

Ràng buộc

  • 1≤n≤m≤105
  • 1≤u,v≤n

Ví dụ

Input Output Giải thích
2 3
1 1
1 2
2 2
1 Hoán vị duy nhất là P=(1,2), dùng các cầu (1,1) và (2,2). Chỉ có thể dỡ cầu (1,2).
3 6
1 1
2 2
3 3
1 2
2 3
1 3
3 Ví dụ bổ sung (không có trong đề gốc). Hoán vị duy nhất là P=(1,2,3), nên có thể dỡ một trong ba cầu (1,2), (2,3), (1,3).

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0