Problem A
Austan Atlantshafs
Languages
en
is
Margar borgir og aðrar stofnanir eiga það til að reisa styttur af ýmsum gerðum til að vekja athygli. Í þessu samhengi eru stærri styttur auðvitað betri, því stærri stytta því meiri athygli. Enn betra er ef styttan er sú stærsta á stóru svæði í kringum punktinn þar sem hún var reist. Sérhver stofnun vil því auglýsa styttuna sína sem ,,stærsta styttan í X“ þar sem X er stærsta nefnda svæðið sem gerir þetta að sannri staðhæfingu. Til dæmis ef stytta væri stærst í allri Evrópu væri það mun betri auglýsing en að segja að það sé stærsta stytta Íslands, þó það væri auðvitað einnig satt ef hún væri staðsett þar. Athugið að ef til dæmis Þýskaland og Frakkland hefðu bæði jafn stórar stærstu styttur, þá væri hvorug þeirra stærsta stytta Evrópu.
Inntak
Fyrsta lína inntaksins inniheldur eina heiltölu $n$, fjöldi landsvæða með $1 \leq n \leq 100,000$. Næst koma $n$ línur þar sem hver þeirra lýsir einu landsvæði. $i$-ta línan inniheldur streng $s_i$, streng $t_i$ og jákvæða heiltölu $x_i$, aðskilin með bilum. $s_i$ gefur nafn $i$-ta svæðisins og $t_i$ gefur nafn svæðisins sem $i$-ta svæðið er innihaldið í. $t_i$ er alltaf eitt af landsvæðunum sem kemur fyrir í inntakinu. $x_i$ gefur svo loks hæð styttunar $i$-ta svæðinu, þar sem $1 \leq x_i \leq 10^9$ ef það er stytta þar og $x_i = -1$ annars. Ef svæðið inniheldur önnur svæði mun $x_i = -1$, en $x_i > 0$ annars. Engin tvö ólík svæði hafa sama nafn.
Sérhver strengur í inntaki er af lengd mest $20$ og inniheldur bara enska lágstafi. Samtals lengd allra strengja í inntaki verður mest $10^6$. Fyrsta svæðið verður ávallt jord og inntakið segir að það sé innihaldið í sjálfu sér. Ekkert annað svæði er innihaldið í sjálfu sér, hvorki beint né gegnum milliliði.
Úttak
Fyrir hvert landsvæði með styttu, prentið nafn stærsta svæðisins þar sem stytta þess er ennþá stærst. Svæði er talið stærra en annað svæði ef það inniheldur hitt svæðið. Prenta skal hvert nafn á sinni eigin línu, og gefa svörin í sömu röð og svæðin eru gefin í inntaki.
| Sample Input 1 | Sample Output 1 |
|---|---|
17 jord jord -1 evropa jord -1 asia jord -1 amerika jord -1 afrika jord -1 eyjaalfa jord -1 thyskaland evropa 100 frakkland evropa 80 kina asia 130 indland asia 70 norduramerika amerika -1 suduramerika amerika -1 kalifornia norduramerika 110 kanada norduramerika 90 brasilia suduramerika 150 sudurafrika afrika 140 astralia eyjaalfa 200 |
evropa frakkland asia indland norduramerika kanada amerika afrika jord |
