trang chủ / đề bài / icpc22_mn_m

Hai đường đặc biệt

Đề bài

Mô tả

Để biến Thành phố Tuyệt vời thành nơi hấp dẫn hơn với du khách, chính quyền đưa ra kế hoạch sau: chọn hai con đường của thành phố và gọi chúng là các ĐƯỜNG ĐẶC BIỆT. Các đường đặc biệt này sẽ được công bố là những địa điểm cực kỳ quan trọng, thu hút du khách khắp thế giới.

Thành phố được biểu diễn bằng một đồ thị với các đỉnh là các ngã tư và các cạnh là các con đường nối hai ngã tư. Đồ thị có tổng cộng n đỉnh và m cạnh, mỗi con đường đi được theo cả hai chiều. Từ một ngã tư bất kỳ có thể đi tới mọi ngã tư khác chỉ bằng các con đường. Mỗi con đường nối hai ngã tư khác nhau và không có hai con đường nào nối cùng một cặp ngã tư.

Để giảm lưu lượng trên các đường đặc biệt, người ta quyết định thu phí trên mỗi đường đặc biệt theo cả hai chiều: mỗi lần đi qua một đường đặc biệt phải trả 1 đồng xu. Các con đường khác không mất phí.

Các nhà phân tích đã thu thập một mẫu gồm k người dân, người thứ i cần đi làm từ ngã tư ui tới ngã tư vi. Sau khi hai đường đặc biệt được chọn, mỗi người sẽ đi làm theo đường đi có chi phí nhỏ nhất.

Để thu được nhiều xu nhất, cần chọn hai con đường làm đường đặc biệt sao cho tổng số xu mà k người dân này phải trả là lớn nhất. Hãy giúp chính quyền: với sơ đồ thành phố và mẫu người dân đã cho, hãy cho biết nên chọn hai con đường nào làm đường đặc biệt, và khi đó người dân sẽ trả tổng cộng bao nhiêu xu.

Dữ liệu vào

Dữ liệu vào gồm nhiều bộ test. Dòng đầu tiên chứa số nguyên t, số bộ test.

Mỗi bộ test có dạng:

  • Dòng đầu tiên chứa hai số nguyên n và m, số ngã tư và số con đường.
  • m dòng tiếp theo, dòng thứ i chứa hai số nguyên si và fi (1≤si,fi≤n, si≠fi) là hai ngã tư được nối bởi con đường thứ i. Không có hai con đường nối cùng một cặp ngã tư, và từ một ngã tư bất kỳ có thể đi tới mọi ngã tư khác.
  • Dòng tiếp theo chứa số nguyên k, số người dân trong mẫu.
  • k dòng tiếp theo, dòng thứ i chứa hai số nguyên ui và vi (1≤ui,vi≤n, ui≠vi): người thứ i đi làm từ ngã tư ui tới ngã tư vi.

Dữ liệu ra

Với mỗi bộ test, in ra:

  • Dòng thứ nhất: tổng số xu mà người dân phải trả.
  • Dòng thứ hai: hai số nguyên x1, y1 là hai ngã tư được nối bởi đường đặc biệt thứ nhất.
  • Dòng thứ ba: hai số nguyên x2, y2 là hai ngã tư được nối bởi đường đặc biệt thứ hai.

Hai ngã tư của mỗi đường đặc biệt có thể in theo thứ tự bất kỳ. Mỗi đường được in phải là một trong m con đường của thành phố, và hai đường được chọn phải khác nhau. Nếu có nhiều cách chọn tối ưu, in cách bất kỳ.

Ràng buộc

  • 1≤t≤105.
  • 3≤n≤5×105, n−1≤m≤5×105, m≤n(n−1)2.
  • 1≤k≤5×105.
  • Tổng m trên mọi bộ test và tổng k trên mọi bộ test đều không vượt quá 5×105.

Ví dụ

Input Output Giải thích
2
5 5
1 2
2 3
3 4
4 5
5 1
6
1 5
1 3
1 3
2 4
2 5
5 3
6 5
1 2
2 3
2 4
4 5
4 6
3
1 6
5 3
2 5
5
1 5
3 2
5
4 2
5 4
Bộ thứ nhất: chọn đường 1−5 và 3−2 thì vòng tròn bị cắt thành hai phần {1,2} và {3,4,5}; năm người có hai đầu ở hai phần khác nhau mỗi người trả 1 xu. Bộ thứ hai: chọn 2−4 và 4−5, người đi 1→6 trả 1 xu, hai người còn lại mỗi người trả 2 xu. (Đề gốc ghi nhầm t=3.)
1
3 2
1 2
2 3
2
1 3
2 3
3
1 2
2 3
Ví dụ bổ sung (không có trong đề gốc). Cả hai con đường đều được chọn: người đi 1→3 trả 2 xu, người đi 2→3 trả 1 xu.

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