trang chủ / đề bài / icpc20_nat_c

Cáp treo

Đề bài

Mô tả

Với độ cao 3147,3 mét, Fansipan là ngọn núi cao nhất bán đảo Đông Dương. Để thúc đẩy du lịch, người ta xây dựng n nhà ga trên núi, đánh số từ 1 đến n.

Hai công ty Mobi và Vina phụ trách vận hành các tuyến cáp treo nối các nhà ga. Mỗi công ty có k tuyến cáp treo. Tuyến cáp treo thứ i của Mobi nối hai nhà ga MSi và MEi. Tuyến cáp treo thứ i của Vina nối hai nhà ga VSi và VEi.

Hai nhà ga được gọi là được kết nối bởi một công ty khi và chỉ khi có thể đi từ nhà ga này đến nhà ga kia chỉ bằng các tuyến cáp treo của công ty đó. Để hợp tác hòa bình, hai công ty thống nhất các điều kiện sau:

  • Với mọi i hợp lệ, MSi<MEi và VSi<VEi.
  • Các MSi đôi một khác nhau, các MEi đôi một khác nhau.
  • Các VSi đôi một khác nhau, các VEi đôi một khác nhau.
  • Với mọi i≠j, nếu MSi<MSj thì MEi<MEj.
  • Với mọi i≠j, nếu VSi<VSj thì VEi<VEj.
  • Không có cặp nhà ga nào được kết nối bởi cả hai công ty. Nói cách khác, với mọi cặp nhà ga i và j, nếu i và j được kết nối bởi Mobi thì chúng không được kết nối bởi Vina, và ngược lại.

Cho n và k, hãy kiểm tra xem có thể để Mobi và Vina mỗi công ty vận hành k tuyến cáp treo thỏa mãn tất cả các điều kiện trên hay không.

Dữ liệu vào

Một dòng chứa hai số nguyên n và k, cách nhau bởi một dấu cách (1≤k<n≤100).

Dữ liệu ra

Nếu không thể thỏa mãn tất cả các điều kiện, in ra NO. Ngược lại, in ra YES, tiếp theo là 2·k dòng. Trong k dòng đầu, dòng thứ i chứa hai số nguyên MSi và MEi. Trong k dòng cuối, dòng thứ i chứa hai số nguyên VSi và VEi.

Nếu có nhiều cách, in ra cách bất kỳ.

Ràng buộc

  • 1≤k<n≤100.

Ví dụ

Input Output Giải thích
3 1 YES
1 2
1 3
Mobi nối nhà ga 1 với 2, Vina nối nhà ga 1 với 3. Không cặp nhà ga nào được cả hai công ty kết nối.
3 2 NO Mỗi công ty có 2 tuyến nên kết nối cả 3 nhà ga với nhau; khi đó mọi cặp nhà ga đều được cả hai công ty 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