Manuals are often difficult to read because of the order in which new concepts appear. Let us assume that the part of the manuals we are interested in is a permutation of a set of entries.
An entry has a (unique) keyword and a description, which can explicitly refer to other entries. We say that an entry e2 depends on an entry e1 when the description of e2 mentions e1. If that is the case, e1 must occur before e2 in the permutation, that is, e1 is printed before e2. Remark that dependencies between entries are cycle-free.
For the sake of readability, two additional rules are considered to define the user-friendliest permutation of a set of entries. Let then e1 and e2 be two entries that could be printed at some point according to the existent dependencies.
Let us see an example with the entries and the dependencies depicted in the figure bellow. From now on, entry descriptions are omitted and entry keywords are integers (and compared as integers in the context of rule (b)). An edge from e1 to e2 means that e2 depends on e1.
The following table shows that 0 1 2 6 is the beginning of the corresponding user-friendliest permutation. Since entries 0, 1, 3 and 8 do not depend on any entry, rule (a) cannot determine the first two selections, which are justified by rule (b). The third selection is entry 2 because 2 depends on 1, 1 was the previous selection, and all the entries on which 3 (respectively, 8) depends, which are none, appear before 1. Then, when dependencies allow 3, 6, 7 and 8 to be chosen, rule (a) eliminates entries 3 and 8, and the tie between 6 and 7 is broken by rule (b).
|Possible entries due to dependencies||User-friendliest selection||Justification|
|0, 1, 3, 8||0||(b)|
|1, 3, 8||1||(b)|
|2, 3, 8||2||(a)|
|3, 6, 7, 8||6||(a) and (b)|
The first line of the input contains two integers, E and D, separated by a single space. E is the number of entries and D is the number of dependencies. Entries are identified by integers, ranging from 0 to E − 1.
Each of the following D lines contains two integers, e1 and e2, which indicate that entry e2 depends on entry e1. The two integers are separated by a single space.
10 8 3 4 8 5 3 5 4 9 5 9 1 2 2 7 2 6
0 1 2 6 7 3 4 8 5 9