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$X$ se je uvrstil neposredno pred tekmovalca Y$Y$." To lahko pomeni, da je tekmovalec X$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$N$. V naslednjih N$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$10$ znakov.

Sledi celo število P$P$, tj. število poročanj. Poročanja so opisana v naslednjih P$P$ vrsticah. Vsako poročanje komentatorja je podano z imenoma dveh različnih tekmovalcev X_i$X_i$ in Y_i$Y_i$. Imeni sta ločeni s presledkom.

Omejitve vhodnih podatkov

• 2 \leq N, P \leq 200\;000$2 \leq N, P \leq 200\;000$

Izhodni podatki

Izpišite končni vrstni red tekmovalcev. Vsako ime izpišite v svoji vrstici.

Primer

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

Gajser
Cairoli
Paulin
Herlings
Febvre
Nagl