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

可复制的 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