Prehitevanje

Osnovne informacije

Omejitve
  • Čas: 4 s
  • Spomin: 256 MB
Avtor:
  • Tomaž Hočevar
  • UPM 2018

Pošlji rešitev



Tvoji rezultati.
Nisi poslal še nobene rešitve.
Več »

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

Vhod

6
Gajser
Cairoli
Nagl
Febvre
Herlings
Paulin
4
Febvre Gajser
Nagl Paulin
Febvre Nagl
Paulin Herlings

Izhod

Gajser
Cairoli
Paulin
Herlings
Febvre
Nagl
Tip: Log in to
  • submit and test your solution
  • post or read questions and answers about this task