Prehitevanje
Na tekmovanjih v motokrosu pride običajno do precej prehitevanj in sprememb vrstnega reda tekmovalcev. Motokrosist lahko s posameznim manevrom prehiti enega ali več tekmovalcev, ali pa v svoji želji po napredku zaradi napake izgubi kakšno mesto. Komentator tekme vse spremembe sporoča v obliki: "Tekmovalec X se je uvrstil neposredno pred tekmovalca Y." To lahko pomeni, da je tekmovalec X napredoval, nazadoval, ali pa celo ni prišlo do spremembe njegove uvrstitve.
Napišite program, ki bo spremljal obvestila komentatorja tekme in izračunal končni vrstni red tekmovalcev.
Vhodni podatki
V prvi vrstici se nahaja število tekmovalcev N. V naslednjih N vrsticah so podana imena tekmovalcev od trenutno prvega do zadnjega. Imena tekmovalcev so sestavljena iz malih in velikih črk angleške abecede in niso daljša od 10 znakov.
Sledi celo število P, tj. število poročanj. Poročanja so opisana v naslednjih P vrsticah. Vsako poročanje komentatorja je podano z imenoma dveh različnih tekmovalcev X_i in Y_i. Imeni sta ločeni s presledkom.
Omejitve vhodnih podatkov
- 2 \leq N, P \leq 200\;000
Izhodni podatki
Izpišite končni vrstni red tekmovalcev. Vsako ime izpišite v svoji vrstici.
Primer
Vhod6 Gajser Cairoli Nagl Febvre Herlings Paulin 4 Febvre Gajser Nagl Paulin Febvre Nagl Paulin Herlings | IzhodGajser Cairoli Paulin Herlings Febvre Nagl |
- submit and test your solution
- post or read questions and answers about this task