trang chủ / đề bài / icpc21_nat_d

Những tour riêng biệt

Đề bài

Mô tả

Thành phố Hà Nội có n điểm tham quan, được đánh số từ 1 đến n. Có m con đường hai chiều nối các điểm tham quan. Các con đường này tạo thành một đơn đồ thị: không có hai con đường nào nối cùng một cặp điểm, và không có con đường nào nối một điểm với chính nó.

Mỗi con đường được trang trí bằng một loại cây khác nhau. Hạnh là người yêu cây và muốn tạo ra một tập gồm k tour thỏa mãn:

  • Mỗi tour là một chu trình độ dài t (t>2) đi qua t điểm tham quan p1,p2,…,pt. Cụ thể hơn:
    • với mọi i mà 1≤i≤t−1, pi và pi+1 phải được nối trực tiếp bởi một con đường;
    • pt và p1 cũng phải được nối trực tiếp bởi một con đường;
    • các pi đôi một phân biệt.
  • Mỗi tour phải có ít nhất một con đường không thuộc bất kỳ tour nào trong k−1 tour còn lại.

Hạnh nhận ra rằng có thể không tạo được tập tour như vậy với mạng lưới đường hiện tại. Vì vậy, Hạnh muốn xây thêm một số con đường hai chiều sao cho:

  • Tập đường mới (gồm cả đường xây thêm và đường ban đầu) vẫn tạo thành một đơn đồ thị: không có hai con đường nào nối cùng một cặp điểm, và không có con đường nào nối một điểm với chính nó.
  • Số con đường xây thêm là ít nhất.

Hãy giúp Hạnh xây thêm đường và tạo một tập k tour.

Dữ liệu vào

  • Dòng đầu tiên chứa ba số nguyên n, m và k.
  • m dòng tiếp theo, mỗi dòng chứa hai số nguyên u và v (1≤u,v≤n), cho biết ban đầu có một con đường nối hai điểm u và v. Dữ liệu đảm bảo m con đường này tạo thành một đơn đồ thị.

Dữ liệu ra

Nếu không thể tạo một tập k tour dù Hạnh xây thêm đường như thế nào, in ra một dòng duy nhất chứa từ NO. Ngược lại:

  • Dòng đầu tiên chứa từ YES.
  • Dòng thứ hai chứa một số nguyên w, số con đường xây thêm ít nhất.
  • w dòng tiếp theo, mỗi dòng chứa hai số nguyên x và y (1≤x,y≤n), cho biết xây thêm một con đường nối hai điểm x và y.
  • k dòng cuối cùng, mỗi dòng mô tả một tour theo định dạng sau:
    • Số nguyên đầu tiên là t, số điểm tham quan của tour.
    • t số nguyên tiếp theo là p1,p2,…,pt, các điểm tham quan của tour.

Nếu có nhiều phương án tối ưu, bạn có thể in ra phương án bất kỳ.

Ràng buộc

  • 3≤n≤50.
  • 0≤m≤n(n−1)2.
  • 0≤k≤2000.

Ví dụ

Input Output Giải thích
4 4 3
1 2
1 3
1 4
2 4
YES
2
2 3
3 4
3 2 1 3
3 2 1 4
3 3 1 4
Xây thêm hai đường (2,3) và (3,4). Ba tour 2→1→3, 2→1→4, 3→1→4 lần lượt có đường riêng (2,3), (2,4), (3,4) không thuộc hai tour còn lại.
3 3 3
1 2
1 3
2 3
NO Các đường hiện tại tạo thành đồ thị đầy đủ nên không thể xây thêm đường nào. Chỉ có thể tạo 1 tour dùng tất cả các đường hiện có.

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