Задача №114010. Петя и метро
Волею судеб, однажды Петя попал в город, где открылся новый метрополитен – "МетроДрево", как его называют в городе. Причина такого названия заключается в следующих свойствах:
- Метро состоит из n станций и n - 1 туннелей, каждый их которых соединяет ровно две станции;
- По каждому туннелю курсируют поезда в обе стороны;
- К каждой станции может подходить неограниченное число туннелей;
- От каждой станции можно доехать до любой станции (возможно, с пересадками).
Петя всегда очень любил метро. Воспользовавшись тем, что поезда ездят быстро, а станций (пока) не очень много, юный путешественник перебрал все неупорядоченные пары станций и для каждой пары совершил поездку от одной станции к другой, проезжая при этом минимальное число туннелей. Оказалось, что в совокупности Петя проехал ровно m туннелей.
Петя так увлекся поездками, что, собираясь домой, забыл в гостинице схему метро! Вернувшись домой, Петя решил восстановить схему, используя числа n и m и считая, что все станции занумерованы от 1 до n . Помогите ему!
В единственной строке записаны два числа n , 2 ≤ n ≤ 20 , и m , 1 ≤ m ≤ 10000 .
Если Петя ошибся (а такое, к сожалению, возможно), и удовлетворяющей условию задачи схемы не существует, выведите в единственной строке слово NO. Иначе, выведите в первой строке слово YES, после чего в n - 1 последующих строчках выведите по паре натуральных чисел от 1 до n - номеров станций, соединяемых очередным туннелем. Туннели можно выводить в любом порядке, равно как и станции для каждого туннеля. Если таких схем несколько, выведите любую.
Подзадача 1 (10 баллов): \(m \le 20\).
Подзадача 2 (30 баллов): \(n \le 10\).
Подзадача 3 (60 баллов): нет доп. ограничений.
3 4
YES 1 2 2 3
3 5
NO