ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Romanian Open Contest December 2001

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

C. Pairs

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
A Romanian software company has bought N computers, which are going to be connected so that they may form a network. A connection can be made between any 2 distinct computers and is bidirectional (if the 2 computers are labeled i and j, then data can be sent both from i to j and from j to i). Your job is to determine a way to connect all the N computers, in such a way that every 2 computers will be able to send data between them (directly or using other computers as intermediate devices).
There is only one extra requirement: the network must contain exactly K critical pairs. A pair (i, j) is critical if there exists a connection which, if removed, data communication between i and j will become impossible.

Исходные данные

The input consists of 2 integer numbers: N (1 ≤ N ≤ 100), the number of computers the network will contain and K (0 ≤ K ≤ N*(N-1)/2), the number of critical pairs the network will contain.

Результат

You should output the connections which form the network, one connection per line. A connection is described by a pair (i, j), which means that i and j are directly connected. The 2 numbers of the pair should be separated by a blank. If you cannot build a network which contains exactly K critical pairs, then you should output -1.

Пример

исходные данныерезультат
7 12
1 2
1 3
2 3
3 4
4 5
4 6
4 7
5 6
5 7
6 7
Автор задачи: Mugurel Ionut Andreica
Источник задачи: Romanian Open Contest, December 2001
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1169. Pairs