Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Совершенно секретно

(Время: 1 сек. Память: 16 Мб Сложность: 66%)

В секретном 240 отделе ИПФ РАН N сотрудников и N компьютеров. В отделе вводятся новые требования к секретности. В соответствии с этими требованиями, для каждого сотрудника будут определены ровно K компьютеров, к которым этот сотрудник будет иметь допуск (т.е. за которыми этот сотрудник будет иметь право работать), причём так, что к каждому компьютеру будут иметь допуск ровно K сотрудников.

Информация о том, какой сотрудник к какому компьютеру будет иметь допуск, будет известна лишь непосредственно перед вступлением новых требований в силу. Таким образом, чтобы не прерывать работу отдела, сотрудники должны будут быстро решить, кто за каким компьютером будет работать. Для этого им необходимо заранее написать программу, которая по любому распределению допусков сотрудников найдёт рассадку сотрудников по компьютерам, удовлетворяющую этим допускам.

Обратите внимание, что значение K тоже будет известно лишь в последний момент. Из общих соображений секретности известно лишь, что K будет равняться или 1, или 2, или 4; поэтому ваша программа должна уметь работать для любого из этих трех значений K.

Входные данные

В первой строке входного файла INPUT.TXT записаны натуральные числа N и K (1 ≤ N ≤ 500). Далее следуют K∙N строк, в каждой из которых записаны два натуральных числа – номер сотрудника и номер компьютера, к которому этот сотрудник имеет допуск.

Гарантируется, что каждый сотрудник имеет допуск ровно к K компьютерам, что к каждому компьютеру ровно K сотрудников имеют допуск, и что K равно либо 1, либо 2, либо 4.

Выходные данные

В выходной файл OUTPUT.TXT выведите N строк, в каждой по два числа –номер сотрудника и номер компьютера, за которым он должен работать. Строки можно выводить в произвольном порядке.

Если есть несколько решений, выведите любое. Можно доказать, что для любого входного файла, удовлетворяющего указанным ограничениям, всегда имеется как минимум одно решение.

Примеры

INPUT.TXTOUTPUT.TXT
13 1
2 3
3 1
1 2
3 1
1 2
2 3
22 2
1 2
2 1
2 2
1 1
1 2
2 1

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Введение
 Целочисленная арифметика
 Алгоритмы сортировки
 Длинная арифметика
 C++ Standard Template Library
 Динамическое программирование
 Комбинаторика
 Вычислительная геометрия
 Строки
 Структуры данных
 Теория графов - 1
 Теория графов - 2
 Алгоритм Флойда
 Алгоритм Форда-Беллмана
 Алгоритм Дейкстры
 Минимальный каркас
 Эйлеров цикл, конденсация
 Паросочетания
 A. Банкет
 B. Совершенно секретно
 C. Кубики
 D. Задача о назначениях
 E. Расшифровка

Красноярский краевой Дворец пионеров, (c)2006 - 2020, E-mail: admin@acmp.ru