Problem D
Import Spaghetti

cc-by NCPC 2017

As you sit down and think, you decide that the first thing to do is to eliminate the cycles in the dependency graph. So you start by finding a shortest dependency cycle.

Input

The first line of input contains a number $n$, $1 \le n \le 500$, the number of files. Then follows one line with $n$ distinct names of files. Each name is a string with at least $1$ and at most $8$ lower case letters ‘a’ to ‘z’. Then follow $n$ sections, one section per file name, in the order they were given on the second line. Each section starts with one line containing the name of the file and an integer $k$, followed by $k$ lines, each starting with “import”.

Each “import” line is a comma-space separated line of dependencies. No file imports the same file more than once, and every file imported is listed in the second line of the input. Comma-space separated means that every line will start with “import”, then have a list of file names separated by “, ” (see sample inputs for examples). Each import statement is followed by at least one file name.

Output

If the code base has no cyclic dependencies, output “SHIP IT”. Otherwise, output a line containing the names of files in a shortest cycle, in the order of the cycle (i.e., the $i$th file listed must import the $(i+1)$st file listed, and the last file listed must import the first). If there are many shortest cycles, any one will be accepted.

4
a b c d
a 1
import d, b, c
b 2
import d
import c
c 1
import c
d 0

c

5
classa classb myfilec execd libe
classa 2
import classb
import myfilec, libe
classb 1
import execd
myfilec 1
import libe
execd 1
import libe
libe 0

SHIP IT

5
classa classb myfilec execd libe
classa 2
import classb
import myfilec, libe
classb 1
import execd
myfilec 1
import libe
execd 1
import libe, classa
libe 0

classa classb execd