trang chủ / đề bài / icpcwf25_e

Dịch vụ giao hàng

Đề bài

Mô tả

Công ty Bưu kiện Liên thành phố Caspian (ICPC) đang mở một dịch vụ giao hàng giữa các thành phố quanh biển Caspian. Công ty dự định thuê các người đưa hàng để mang bưu kiện giữa các thành phố này.

Mỗi người đưa hàng có một thành phố nhà và một thành phố đích, và mọi người đưa hàng có cùng một lịch trình di chuyển: rời thành phố nhà lúc 9:00, đến thành phố đích lúc 12:00, rời thành phố đích lúc 14:00 và trở về thành phố nhà lúc 17:00. Trong khi đang ở thành phố nhà hoặc thành phố đích, họ có thể nhận bưu kiện từ khách hàng và/hoặc giao bưu kiện cho khách hàng. Họ cũng có thể trao bưu kiện cho, hoặc nhận bưu kiện từ, những người đưa hàng khác đang có mặt ở cùng thành phố vào cùng thời điểm. Vì ICPC là dịch vụ tận tay, bưu kiện không bao giờ được để lại ở kho hay nơi nào khác để lấy sau: trừ khi bưu kiện đã tới đích, người đưa hàng phải hoặc tự giữ bưu kiện (trong ngày hoặc qua đêm), hoặc trao nó cho một người đưa hàng khác.

Công ty sẽ chỉ đạo các người đưa hàng trao tay bưu kiện sao cho mọi bưu kiện luôn có thể được giao tới đích. Ít nhất là họ hy vọng như vậy!

Ta nói hai thành phố u và v được kết nối nếu có thể giao một bưu kiện từ thành phố u tới thành phố v và cũng có thể giao từ v tới u. Để đánh giá hiệu quả của quá trình tuyển dụng, sau mỗi lần thuê thêm một người đưa hàng, công ty muốn biết số cặp thành phố (u,v) được kết nối (1≤u<v≤n).

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên n và m, trong đó n (2≤n≤2·105) là số thành phố và m (1≤m≤4·105) là số người đưa hàng sẽ được thuê. Các người đưa hàng được đánh số từ 1 đến m theo thứ tự được thuê.

Tiếp theo là m dòng, dòng thứ i chứa hai số nguyên phân biệt ai và bi (1≤ai,bi≤n), lần lượt là thành phố nhà và thành phố đích của người đưa hàng thứ i.

Dữ liệu ra

In ra m số nguyên, mỗi số trên một dòng: số cặp thành phố được kết nối sau khi đã thuê 1,2,…,m người đưa hàng đầu tiên.

Ràng buộc

  • 2≤n≤2·105, 1≤m≤4·105.
  • 1≤ai,bi≤n, ai≠bi.

Ví dụ

Input Output Giải thích
4 4
1 2
2 3
4 3
4 2
1
2
4
6
Sau người thứ nhất, thành phố 1 và 2 được kết nối. Sau người thứ hai, 2 và 3 được kết nối, nhưng 1 và 3 thì chưa: hai người đưa hàng (đi giữa 1,2 và giữa 2,3) không bao giờ gặp nhau. Sau người thứ ba, thêm các cặp (3,4) và (2,4); chẳng hạn từ 2 tới 4: lúc 19:00 trao bưu kiện cho người thứ hai ở thành phố 2; trưa hôm sau người này tới thành phố 3 và trao cho người thứ ba cũng đang ở đó; lúc 18:00 người thứ ba mang bưu kiện về thành phố 4. Sau người thứ tư, cả 6 cặp đều được kết nối.
3 3
1 2
2 1
3 1
1
1
3
Người thứ hai (nhà ở 2, đích ở 1) không gặp người thứ nhất (người thứ nhất ở 1 khi người thứ hai ở 2 và ngược lại), nên vẫn chỉ có cặp (1,2). Người thứ ba ở thành phố 1 vào buổi trưa, gặp người thứ hai, nên cả ba cặp đều được kết nối.

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