For a trip abroad, you need to get several certificates from a state institution. However, it turned out that in order to obtain these certificates, other certificates are needed, and those, in their in turn, need other references. You have to wait in line to get each certificate, so you want to save money time without standing in line for nothing (if you will not have the necessary information while standing in alternately, you will be denied the issuance of this card). Having information about which references are needed for which, determine the optimal the procedure for obtaining all references, in which you will never be refused issues If there are several such optimal options, any one of them will be displayed.
Each of the N lines of the input file govern.in contains two words separated by a space — the name of the certificate and the certificate that must be obtained before it. • There can be from 1 to 100,000 lines. • Words are from 1 to 50 letters long and consist of numbers 0-9 and lowercase letters of the Latin alphabet from a to z. • If for one reference it is necessary to get N others, the file will contain N lines, that will start with the same word. • There is guaranteed to be at least one procedure for obtaining references in which it is possible get all the references. …
The output file govern .out should contain M lines — the names of the references in their order recommended receipt.
Note: The last word must also be followed by a newline character (new- line).