Система пересекающихся множеств
(Время: 1 сек. Память: 16 Мб Сложность: 35%)
На вступительном экзамене в один из крупнейших университетов нашей страны Вам предложили реализовать структуру данных для хранения множеств натуральных чисел.
Структура данных должна хранить n множеств, в каждое из которых могут входить натуральные числа от 1 до m, при этом одно и то же число может принадлежать нескольким множествам одновременно. Необходимо реализовать операции добавления элемента в множество, вывода всех элементов множества и вывода номеров всех множеств, в которых лежит данный элемент.
Реализуйте описанную структуру данных.
Входные данные
Первая строка входного файла INPUT.TXT содержит натуральные числа m и n (1 ≤ m, n ≤ 100). Вторая строка входного файла содержит натуральное число k –количество операций со структурой данных, которые необходимо выполнить (0 ≤ k ≤ 105).
Последующие k строк описывают эти операции. Описание операции может иметь один из трех форматов:
- ADD element set – добавить элемент element (1 ≤ element ≤ m) в множество номер set (1 ≤ set ≤ n);
- LISTSET set – вывести все элементы множества номер set (1 ≤ set ≤ n);
- LISTSETSOF element – вывести номера всех множеств, содержащих элемент element (1 ≤ element ≤ m).
Общее количество операций LISTSET и LISTSETSOF не превышает 1000.
Выходные данные
Для каждой операции LISTSET или LISTSETSOF в выходной файл OUTPUT.TXT выведите соответствующий список элементов (или номеров множеств) в порядке возрастания. Если список пуст, выведите -1. Порядок вывода должен соответствовать порядку, в котором операции заданы во входном файле.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 10 10
5
ADD 1 1
ADD 1 2
ADD 2 1
LISTSET 1
LISTSETSOF 1 | 1 2
1 2 |
| 2 | 10 10
3
ADD 1 1
LISTSET 10
LISTSET 1 | -1
1 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
