Реконструкция иерархии отделов по парам подчинения

Python Сложный dicts

Задача «Реконструкция иерархии отделов по парам подчинения»

Даны пары подчинения сотрудников в формате 'начальник:подчиненный'. Необходимо восстановить полную иерархическую структуру отделов. Каждый сотрудник может иметь несколько подчиненных, но только одного начальника (кроме корневого директора). Входные данные могут содержать циклы или неполные данные — такие случаи нужно игнорировать. Вывести для каждого отдела (самый верхний начальник в цепочке) список всех сотрудников этого отдела в алфавитном порядке, разделенных пробелом. Отделы отсортировать по названию начальника отдела.

Формат ввода

Первая строка содержит целое число N (1 ≤ N ≤ 10000) — количество пар. Затем N строк, каждая вида: 'начальник:подчиненный' (латиница, длина от 1 до 20 символов).

Формат вывода

Для каждого отдела вывести строку: 'начальник отдела: сотрудник1 сотрудник2 ...' (все сотрудники отдела, включая самого начальника, в алфавитном порядке). Отделы отсортировать по имени начальника. Если данные противоречивы (цикл, несколько начальников), то выводится только непротиворечивая часть.

Примеры

Пример 1

ВВОД

4
Alice:Bob
Alice:Charlie
Bob:David
Charlie:Eve

ВЫВОД

Alice: Alice Bob Charlie David Eve

Пример 2

ВВОД

3
X:Y
Y:Z
Z:X

ВЫВОД

Пример 3

ВВОД

2
M:N
M:O

ВЫВОД

M: M N O

Пример 4

ВВОД

ab3c2

ВЫВОД

abababcc

main.py