题目描述

You work at ECorp and your Human Resources department is migrating employee data from an on-premise system provided by Hooli to a new Cloud Native solution provided by a fresh startup Pied Piper. Sadly the new system does not yet have feature parity with the old one and they need your help to store and display the entire management structure. The system is lean and conscious of resource usage so they can only afford to increase their storage by two kilobits.

输入格式

The first line of the input will be a command to execute either ENCODE or DECODE.

Encode

You will receive lines describing managers and their direct reports/subordinates. All lines will start with the name of the manager, followed by a colon, followed by a space-separated list of their direct reports ordered from their most to least favorite. Colons have a trailing space. No manager is listed before their manager, if they have one.

Decode

In the decode case you will be given the output that your program printed in the encode case: a list of all employee names in an arbitrary order, one per line, followed by a single line with a binary string $B$.

输出格式

Encode

Your program must first output the names of all the employees, one per line in an arbitrary order (this was a requirement from upper management). One additional line is dedicated for your encoding string $B$ which must consist of ones and zeros and not exceed 2048 characters.

Decode

Output the original structure in the same format as it was originally given. The order of manager definitions does not have to be the same, but every one must come after their manager if they have one. However, the order of reports for any specific manager has to remain the same (from their most to least favorite).

ENCODE
Janez: Josip Zofia
Zofia: Karolina

Josip
Karolina
Janez
Zofia
00101100

DECODE
Josip
Karolina
Janez
Zofia
00101100

Janez: Josip Zofia
Zofia: Karolina

提示

Comment

The encoding in the example above uses two consecutive characters for every person as they are ordered in the list. $11$ denotes the CEO (Janez). $00$ denotes a person at the second level of hierarchy. Their order in the CEO's list of direct reports is the same as in the encoded list of names (Josip and Zofia). Luckily, there are just two in this case. $10$ denotes Zofia's report and $01$ would denote Josip's reports, which he does not have.

Input limits

• $2 \leq \text{number of all employees at EC} \leq 600$
• $|B| \leq 2048$
• Employee names are at most 10 characters long and consist of upper and lower case letters of the English alphabet.
• There is exactly one employee without a manager (the company CEO) and no employee has more than one manager.