Event Ordering

You are given a set of events. Each event is identified by an id and may have prerequisites – events that must be completed before this event can be executed. Your task is to determine an order to complete all the events such that every event is scheduled after all its prerequisites.

If there exists an ordering that satisfies all these dependencies, print the event ids in order separated by a space. Otherwise, if the dependency graph contains a cycle and no valid ordering exists, print impossible.

The dependencies can be interpreted using the famous topological sort algorithm. In mathematical notation, given events \(E = \{e_1,e_2,\dots,e_n\}\) and a relation \(R\) such that \(e_i R e_j\) if event \(e_i\) is a prerequisite for event \(e_j\), your goal is to find a permutation \(\pi\) of \(E\) such that for any two events \(e_i\) and \(e_j\) if \(e_i \in prerequisites(e_j)\) then \(\pi(e_i) < \pi(e_j)\).

inputFormat

The input is read from standard input. The first line contains an integer n denoting the number of events. Each of the next n lines describes an event in the following format:

event_id k prereq_1 prereq_2 ... prereq_k

Here, event_id is a string identifying the event, k is an integer indicating the number of prerequisites for this event, followed by k strings representing the prerequisite event IDs.

outputFormat

Output to standard output a single line. If a valid ordering exists, print all the event IDs in one line separated by a single space, representing one valid order of completion. If no valid ordering exists (i.e. there is a cycle), output the string impossible.

2
event1 0
event2 0

event1 event2