На уроках географии в школе Вам наверняка рассказывали о Стране Дураков. В частности, Вы должны знать, что внутреннее устройство Страны Дураков не менялось на протяжении многих столетий. Страна состоит из n городов, некоторые пары которых соединены двусторонними дорогами, причем каждая из дорог характеризуется величиной li — своей длиной.
Так и жили бы дураки, но недавно в результате государственного переворота в стране поменялся король — им стал медведь Василий. Василий разделил города страны на области таким образом, что между любыми двумя городами из одной области существует путь по дорогам страны, а между двумя городами из разных областей такого пути нет. После этого Василий решил провести дорожную реформу: построить в стране ровно p новых дорог. Строительство одной дороги происходит следующим образом:
- Выбирается пара различных городов u, v, которые будет соединять новая дорога (при этом возможно, что между этими городами уже существует дорога).
- Определяется длина новой дороги: если города u, v относятся к различным областям, то длина вычисляется как min(109, S + 1) (S — суммарная длина всех дорог, существующих в соединяемых областях), иначе длина полагается равной 1000.
- Между выбранными городами строится дорога указанной длины. Если новая дорога соединяла различные области, то после ее строительства эти две области будут объединены в одну.
Василий хочет, чтобы после проведения дорожной реформы страна состояла ровно из q областей. Ваша задача — разработать для медведя Василия такой план строительства дорог, удовлетворяющий этому требованию, чтобы суммарная длина построенных дорог была минимально возможной.
Выходные данные
Если невозможно требуемым образом построить дороги, выведите единственную строку «NO» (без кавычек). В противном случае выведите в первую строку слово «YES» (без кавычек), а в следующих p строках приведите план строительства дорог. Каждая строка плана должна состоять из двух различных целых чисел, задающих номера городов, которые соединяет очередная дорога. Дороги в плане должны следовать в том порядке, в котором их нужно строить. Если существует несколько оптимальных решений, можно вывести любое.
Примечание
Рассмотрим первый пример. До начала реформы Страна Дураков состоит из четырех областей. Первая область включает в себя города 1, 2, 3, вторая — города 4 и 6, третья — города 5, 7, 8, четвертая — город 9. Суммарная длина дорог, существующих в этих областях, составляет 11, 20, 5 и 0 соответственно. Согласно плану, первой строится дорога длины 6 между городами 5 и 9, а второй — дорога длины 23 между городами 1 и 9. Таким образом, суммарная длина построенных дорог составляет 29.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
9 6 2 2
1 2 2
3 2 1
4 6 20
1 3 8
7 8 3
5 7 2
|
YES
9 5
1 9
|
|
2
|
2 0 1 2
|
NO
|
|
3
|
2 0 0 2
|
YES
|