H. Human Resources
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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.

Input

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$$$.

Input limits

  • $$$2 \leq$$$ number of all employees at ECorp $$$\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.
Output

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).

Examples
Input
ENCODE
Janez: Josip Zofia
Zofia: Karolina
Output
Josip
Karolina
Janez
Zofia
00101100
Input
DECODE
Josip
Karolina
Janez
Zofia
00101100
Output
Janez: Josip Zofia
Zofia: Karolina
Note

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.