Hide

Problem B
Managing Packaging

Modern operating system distributions have tools to manage installed software, making it easy to keep the software up-to-date. Putting different pieces of software into ‘packages’ that can be installed separately keeps things simple and avoids duplicate effort and code. But this means that a package may depend on other packages, requiring their installation before that package can be installed. For example, many programs need to use ‘libc,’ which contains standard C-library functions. To keep track of these dependencies, many distributions use some sort of package manager.

When a user wants to install a new package (or set of packages), a package manager takes care of the headache of tracking down which packages are required to install the desired package. Of course, those may also depend on other packages.

For this problem, determine an order (if one exists) that allows a given list of packages to be installed. No package should be installed before all the packages it depends on are installed. You may assume that, at the beginning, no packages have been installed.

Input

Input consists of up to $10$ test cases. Each test case start with a number $1 \le n \le 1\, 000$, which is the number of packages the user wants to install. This is followed by $n$ lines which describe $n$ packages. Each package description starts with the name of the package and is followed by a space-separated list of the package’s unique dependencies. Each package has at most $20$ dependencies, and each is one of the other $n-1$ packages. Each package name is a string of up to $40$ non-whitespace characters using the English alphabet (a-z, A-Z), digits (0-9), as well as the characters _, -, ., and + (i.e. underscore, minus, period, and plus). Input ends when $n$ is zero.

Output

For each test case, output the order of package installation that allow them all to be installed after their respective dependencies. If there are multiple possible orderings, then give the ordering that is lexicographically first (using ASCII values for string ordering). If there is some group of packages that are not able to be ordered within the list, output ‘cannot be ordered’ instead of ordering the packages. Put a blank line between each pair of test cases.

Sample Input 1 Sample Output 1
14
libattr
vim-X11 vim-common gtk2 libattr
vim-common
gtk2 libtiff atk pango glib2
libtiff zlib libjpeg
atk
pango xorg-x11-libs freetype glib2
glib2
zlib
libjpeg
xorg-x11-libs grep freetype
grep pcre
pcre
freetype
3
emacs xorg-x11 lisp
xorg-x11
lisp emacs
0
atk
freetype
glib2
libattr
libjpeg
pcre
grep
vim-common
xorg-x11-libs
pango
zlib
libtiff
gtk2
vim-X11

cannot be ordered
Sample Input 2 Sample Output 2
4
atk pango
glib2 pango
grep atk
pango
0
pango
atk
glib2
grep

Please log in to submit a solution to this problem

Log in