Server Startup Order

You are given a set of n servers and a list of dependencies for each server. Each server i (1-indexed) may depend on some other servers, meaning that those servers must be started before server i can be started.

The dependencies are provided in n lines. Each dependency line consists of some space‐separated integers ending with a -1. All integers before the trailing -1 represent the identifiers of servers that server i depends on. Your task is to determine a valid startup order for all servers. In other words, you must output an ordering of the server identifiers such that every server appears after all the servers it depends on.

If no valid order exists (i.e. there is a cycle in the dependency graph), output Not possible.

Note: The problem can be solved using a topological sort algorithm. The ordering is unique if the algorithm always picks servers with zero incoming edges in increasing order.

Formula: A valid order is an arrangement \(\sigma\) of \(\{1,2,\dots,n\}\) such that for every dependency \(i \to j\), \(\sigma^{-1}(i) < \sigma^{-1}(j)\).

inputFormat

The input is read from stdin and has the following format:

• The first line contains an integer n, representing the number of servers.
• The following n lines each contain a series of space-separated integers representing the dependencies for the i^th server. Each line terminates with a -1 which is not a dependency.

For example:

3
-1
1 -1
2 -1

outputFormat

The output should be written to stdout as a single line.

• If a valid startup order exists, print the server identifiers in the order they should be started, separated by a single space.
• If there is no valid order (i.e. the dependency graph has a cycle), print Not possible.

For instance, for a valid order output:

1 2 3

## sample

3
-1
-1
-1

1 2 3