0254. Дороги

Имя входного файла:	roads.in
Имя выходного файла:	roads.out
Ограничение по времени:	2 s
Ограничение по памяти:	256 megabytes

В одном далеком-предалеком государстве царь решил создать развитое государство, построив каменные дороги, которых раньше у него не было. Царство считается развитым, если в нем не менее m каменных дорог. Царь решил не строить лишние дороги, потому что казенные деньги нужно беречь. При этом он хочет, чтобы из каждого города можно было проехать в любой другой, используя только каменные дороги. В царстве n городов. Между двумя городами нельзя строить несколько каменных дорог. Нельзя также строить дороги, ведущие из города в этот же город. Вас, как главного советника царя, попросили составить план постройки дорог, чтобы выполнялись все условия, поставленные царем.

Формат входного файла

Входной файл содержит 2 целых неотрицательных числа n и m - количество городов в царстве и количество дорог, которое необходимо построить (n ≥ 1). Оба числа не превосходят 10⁵.

Формат выходного файла

В первой строке выходного файла выведите "NO", если построить дороги, согласно требованиям царя невозможно. В противном случае в первой строке выведите "YES" (без кавычек). Далее выведите m строк с описанием возможного расположения дорог. В каждой строке выведите 2 числа - номера городов, между которыми нужно построить дорогу. Если существует несколько решений, выведите любое.

Пример:

roads.in	roads.out
4 4	YES 2 1 1 3 4 3 1 4
10 2	NO

Источник: Командное школьное первенство Республики Карелия по программированию, 4 ноября 2007.

Обсудить       Отправить решение



Версия для печати