Reconstruction of department hierarchy based on subordination pairs

Python Hard dicts

Task «Reconstruction of department hierarchy based on subordination pairs»

Given pairs of employee subordination in the format 'boss:subordinate'. It is necessary to restore the full hierarchical structure of departments. Each employee can have several subordinates, but only one boss (except for the root director). The input data may contain cycles or incomplete data — such cases should be ignored. For each department (the topmost boss in the chain), output a list of all employees of that department in alphabetical order, separated by a space. Sort the departments by the name of the department head.

Input Format

The first line contains an integer N (1 ≤ N ≤ 10000) — the number of pairs. Then N lines, each in the format: 'boss:subordinate' (Latin characters, length from 1 to 20 characters).

Output Format

For each department, output a string: 'department head: employee1 employee2 ...' (all employees of the department, including the head themselves, in alphabetical order). Sort departments by the head's name. If the data is contradictory (cycle, multiple heads), then only the non-contradictory part is output.

Examples

Example 1

INPUT

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

OUTPUT

Alice: Alice Bob Charlie David Eve

Example 2

INPUT

3
X:Y
Y:Z
Z:X

OUTPUT

Example 3

INPUT

2
M:N
M:O

OUTPUT

M: M N O

Example 4

INPUT

ab3c2

OUTPUT

abababcc

main.py