Problem I
Ástarmarghyrningur

Eins og við vitum öll geta sápuóperur með mörgum persónum leitt að alvarlega flóknu ástar drama. Í sérstakri þáttaröð eru $N$ persónur. Hver persóna elskar nákvæmlega eina persónu (sem getur verið hún sjálf). Við segjum að tvær persónur eru í sambandi ef og aðeins ef þær elska hvora aðra.

Ein týpa af flækingum kallast “ástarmarghyrningur”. Við segjum að þrjár eða fleiri persónur eru í “ástarmarghyrning” ef að fyrsta persónan elskar aðra, önnu elskar þá þriðju og svo framvegis, og einnig að síðasta persónan elski þá fyrstu.

Nýlegar kannannir hafa sýnt fram á að áhorfendur séu þreyttir á þessu drama og vilja eitthvað rómantískara. Því var ákveðið að skjóta einhverjar persónur með ástarörvum þannig að allir byrji í sambandi. Með því að skjóta einhvern með ástarör er hægt að breyta hvaða persónu hann elskar (í hvaða persónu sem þú vilt).

Hver er minnsti fjöldi ástarörva sem þarf til að koma öllum í samband?

Inntak

Fyrsta línan inniheldur heiltöluna $N$, fjöldi persónna í þáttaröðinni. Næstu $N$ línur innihalda tvö nöfn aðskilin með bili, $s$ og $t$, sem þýðir að persónan sem heitir $s$ elskar persónuna sem heitir $t$. Nöfn persónna eru í mesta lagi $10$ stafir á lengd og innihalda aðeins enska lágstafi.

Úttak

Skrifaðu út eina heiltölu – minnsta fjölda ástarörva sem þarf til að koma öllum í samband. Ef það er ekki hægt skrifaðu út -1.

Takmarkanir

Lausnin þín verður prófuð á einhvern fjölda prufuhópa, hver hópur gefur einhvern fjölda stiga. Hver hópur inniheldur einhvern fjölda prufutilvika. Til að fá stig fyrir hóp þarftu að leysa öll prufutilvik innan hópsins. Lokastigin eru fengin úr skilunum sem gáfu hæst stig.

Útskýringar á sýnidæmum

Fyrsta sýnidæmið má sjá í myndinni að ofan. Efri parturinn sýnir upphaflegu ástaraðstæðurnar, þar sem ör bendir frá $s$ til $t$ ef að $s$ elskar $t$. Persónurnar sem þarf að skjóta með örvum eru litaðar bleikar. Neðri parturinn sýnir aðstæðurnar eftir að örvunum hefur verið skotið.

Í öðru sýnidæminu (sem tilheyrir hópi 3) eru nokkrar lausnir. Ein af þeim er að skjóta a, b og d með ástarörvum, og láta þau elska b, a og c, í þessarri röð.

Í þriðja sýnidæminu höfum við ástarþríhyrning þar sem það skiptir ekki máli hversu mörgum örvum við skjótum, það verður alltaf einhver skilinn útundan.

8
leonard emmy
ada emmy
isaac leonard
emmy pierre
pierre bernhard
bernhard emmy
sofia karl
karl sofia

3

4
a c
b c
c d
d d

3

3
rocky scarlet
scarlet patrick
patrick rocky

-1