trang chủ / đề bài / icpc22_reg_d

Hẹn hò

Đề bài

Mô tả

Alob và Bice là bạn thân nhiều năm và cuối cùng đã trở thành một cặp! Vì cả hai cùng tham dự kỳ thi ICPC khu vực tại Thành phố Hồ Chí Minh, họ dự định có những buổi hẹn hò lãng mạn ở đó.

Mạng lưới giao thông của Thành phố Hồ Chí Minh gồm n nút giao và m con đường hai chiều. Mỗi con đường nối hai nút giao khác nhau. Ta biết hai điều sau về mạng lưới giao thông:

  • Không có nút giao nào bị cô lập hoàn toàn. Nói cách khác, mỗi nút giao kề với ít nhất một con đường.
  • Mọi con đường đều dài như nhau. Cụ thể, bất kỳ ai cũng mất đúng một phút để đi từ đầu này sang đầu kia của mỗi con đường.

Alob và Bice đang tìm chỗ ở cho cả chuyến đi. Alob có thể chọn một khách sạn gần nút giao x, còn Bice có thể chọn một khách sạn gần nút giao y.

Sau đó cặp đôi thực hiện "hành trình tìm người trong mộng" như sau:

  • Đầu ngày hẹn hò, họ ăn sáng tại khách sạn của mình và rời khách sạn cùng lúc. (Để đơn giản, gọi thời điểm này là "thời điểm 0".)
  • Mỗi người chọn một con đường nối trực tiếp với nút giao chỗ khách sạn của mình và đi theo con đường đó tới một nút giao khác. Một phút sau, họ cùng lúc tới các nút giao mới. Gọi thời điểm này là "thời điểm 1".
  • Nếu hai người nhìn thấy nhau tại cùng một nút giao, hành trình kết thúc. Ngược lại, mỗi người lại chọn một con đường nối trực tiếp với nút giao hiện tại và đi tới một nút giao khác. Họ lại cùng lúc tới nơi sau đúng một phút ("thời điểm 2").
  • Nếu hai người ở cùng một nút giao, hành trình kết thúc. Ngược lại, quá trình trên cứ thế lặp lại...

Tổng quát, sau khi tới một nút giao, mỗi người trước tiên kiểm tra xem người kia có ở đó không. Nếu có, họ đã tìm thấy nhau và quá trình kết thúc. Nếu không, người đó lập tức chọn một con đường kề để đi tới một nút giao khác. Họ không bao giờ đứng yên mà đi liên tục cho tới khi gặp nhau. Vì mỗi nút giao kề với ít nhất một con đường nên luôn có thể chọn một nút giao khác để đi tới. Lưu ý rằng cặp đôi chỉ muốn gặp nhau tại các nút giao, không phải trên đường. Vì vậy, nếu hai người gặp nhau giữa một con đường, họ vẫn tiếp tục đi và quá trình trên vẫn tiếp diễn.

Tùy theo các nút giao chỗ khách sạn của họ, có thể xảy ra hai kịch bản:

  • Sau một khoảng thời gian hữu hạn, hai người có thể tới cùng một nút giao vào cùng một thời điểm, và quá trình kết thúc.
  • Dù hai người chọn đường đi như thế nào, họ cũng không bao giờ gặp nhau tại một nút giao, và quá trình kéo dài mãi mãi.

Cặp đôi muốn biết có bao nhiêu cách chọn khách sạn để kịch bản thứ nhất xảy ra. Nói cách khác, hãy đếm số cặp nút giao (x,y) sao cho nếu Alob chọn khách sạn gần nút giao x và Bice chọn khách sạn gần nút giao y thì họ có thể gặp nhau sau một khoảng thời gian hữu hạn.

Vì Thành phố Hồ Chí Minh đón hàng triệu du khách mỗi năm nên gần nút giao nào cũng có khách sạn. Ngoài ra, Alob và Bice có thể chọn khách sạn gần cùng một nút giao, và khi đó hiển nhiên họ nhìn thấy nhau ngay!

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên n và m (2≤n≤105, 1≤m≤2·105) lần lượt là số nút giao và số con đường.

Mỗi dòng trong m dòng tiếp theo chứa hai số nguyên u và v (1≤u,v≤n, u≠v) cho biết có một con đường nối hai nút giao u và v.

Dữ liệu đảm bảo mỗi nút giao kề với ít nhất một con đường.

Dữ liệu ra

In ra một số nguyên duy nhất là số cách cặp đôi chọn khách sạn để họ có thể gặp nhau sau một khoảng thời gian hữu hạn.

Ràng buộc

  • 2≤n≤105
  • 1≤m≤2·105
  • 1≤u,v≤n, u≠v
  • Mỗi nút giao kề với ít nhất một con đường.

Ví dụ

Input Output Giải thích
5 4
1 2
2 3
3 4
4 5
13 Mạng lưới là đường đi 1−2−3−4−5. Có 13 cách: (1,1), (1,3), (1,5), (2,2), (2,4), (3,1), (3,3), (3,5), (4,2), (4,4), (5,1), (5,3), (5,5). Với (1,3): Alob buộc phải tới nút 2, Bice có thể tới nút 2 hoặc 4; nếu Bice chọn nút 2 thì hai người gặp nhau ở thời điểm 1. Với (4,5): mọi con đường nối một nút lẻ với một nút chẵn, nên ở thời điểm chẵn Alob luôn ở nút chẵn còn Bice luôn ở nút lẻ, ở thời điểm lẻ thì ngược lại; họ không bao giờ gặp nhau.
5 4
1 2
2 3
3 1
4 5
11 Ví dụ bổ sung. Trong tam giác 1,2,3, mọi cặp (x,y) trong 9 cặp đều gặp được nhau, chẳng hạn với (1,2), Alob đi 1→3 và Bice đi 2→3 thì hai người gặp nhau tại nút 3 ở thời điểm 1. Với hai nút 4,5 chỉ có (4,4) và (5,5). Một người ở tam giác và một người ở nút 4 hoặc 5 không bao giờ gặp nhau.

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