← 返回题目列表

Codeforces · 1773/K

K. 国王之谜

中文机器翻译题面 查看原题

以下页面来自赛事官方发布的原题PDF,已完整保存并渲染到本地。

King's Puzzle - 原题 PDF 第 1 页
原题PDF第12页
可复制的 PDF 提取文本
ICPC 2022–2023, NERC – Northern Eurasia Finals
                          St. Petersburg, Barnaul, Kutaisi, Almaty, December 7th, 2022
Problem K. King’s Puzzle

    Time limit:        3 seconds
    Memory limit:     1024 megabytes

King Kendrick is a sovereign ruler of Kotlin Kingdom. He is getting ready for the next session of the
government. Kotlin Kingdom consists of n cities. These cities need to be connected by several bidirectional
roads. Since ministries are responsible for aspects of safety and comfort of the kingdom’s residents, some
of them have made the following requirements:


   • “All the cities should be connected by new roads” — Ministry of Transport and Digital Infrastructure.

   • “There may not be a loop road — a road that connects a city with itself” — Ministry of Environment.

   • “There should be at most one road between a pair of cities” — Treasury Department.

   •  “If ai is the number of roads connected to i-th city, then the set {a1, . . . , an} should consist of exactly
     k distinct numbers” — Ministry of ICPC.


King Kendrick has issues with the requirements from the Ministry of ICPC. He asks you to help him.
Find any set of roads that suits all the requirements above or say that it is impossible.

Input

The only line of the input consists of two integers n and k (1 ≤k ≤n ≤500).

Output

If it is impossible to satisfy all the requirements, output “NO” in the only line.

Otherwise, output “YES” in the first line.
Output m — the number of roads (0 ≤m ≤n·(n−1) ) in the second line.                                                     2
Next m lines should contain pairs of integers a and b — the cities to connect by a road (1 ≤a, b ≤n).

Examples

      standard input            standard output                  notes
 5 2                        YES
                            4
                            1 2
                            1 3
                            1 4
                            1 5

                                                            City 1 has four roads
                                                           connected to it while other
                                                                             cities have exactly one.

 4 1                        YES
                            4
                            1 2
                            2 3
                            3 4
                            4 1

                                                        Every city has exactly two
                                                             roads connected to it.




                                        Page 12 of 13