Задача C. Библиографический каталог

Автор:А. Баранов   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

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

По имеющемуся набору записей требуется определить списки уникальных авторских групп и связанных с ними книг.

Формат входного файла

В начале входного файла "input.txt" содержится натуральное число n, указывающее общее число записей.
Далее идет набор самих записей, представленных в следующем виде:

<имя_автора> <название_книги>

При этом каждая такая запись расположена в отдельной строке.

Формат выходного файла

Выходной файл "output.txt" должен содержать натуральное m, указывающее число уникальных авторов, за которым следует список их имен, расположенных в порядке их первого упоминания в исходном каталоге.

Далее указывается число k, за которым следует ровно k уникальных авторских групп. Каждая группа записана в следующем виде. Вначале указывается число входящих в нее авторов, после чего идут их порядковые номера.
При этом полагается, что нумерация авторов начинается с нуля.

В окончание выходного файла следует записать количество и список уникальных книг, также расположенных в порядке их упоминания. Напротив каждой из них (через пробел) указать номер соответствующей группы.
При этом полагается, что группы авторов нумеруются с нуля.

Ограничения

Полагается, что все имена авторов и названия книг состоят из цифр и букв латинского алфавита.
При этом регистр их написания значения не имеет.

0 < n ≤ 2 ⋅ 104

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
12
Vanya ABC
Danya XYZ
Anton GIT
Vitya Xyz
Daria git
Vahob Git
other 000
vanya 123
vanya abc
danya END
danya 123
vanya End
7
vanya
danya
anton
vitya
daria
vahob
other

5
3 5 2 4
2 1 0
1 6
2 1 3
1 0

6
abc 4
xyz 3
git 0
000 2
123 1
end 1

0.103s 0.025s 15