|
Совершенно секретно
(Время: 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.TXT | OUTPUT.TXT |
|---|
| 1 | 3 1
2 3
3 1
1 2 | 3 1
1 2
2 3 |
| 2 | 2 2
1 2
2 1
2 2
1 1 | 1 2
2 1 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |
