Problem I
Mīlas daudzstūris

Kā mēs visi zinām, TV ziepju operas ar daudziem tēliem var novest pie ļoti sarežģītām mīlas drāmām. Vienā TV šovā ir $N$ tēli. Katrs tēls mīl tieši vienu tēlu, kas var būt arī viņš pats. Mēs sakam, ka divi tēli ir attiecībās tad un tikai tad, ja tie mīl viens otru.

Viens īpašs sarežģītu attiecību veids ir “mīlas daudzstūris“. Mēs sakam, ka 3 vai vairāk tēli ir “mīlas daudzstūrī“, ja pirmais tēls mīl otro, otrais mīl trešo un tā tālāk, kā arī pēdējais tēls mīl pirmo tēlu.

Nesenie aptauju rezultāti rāda, ka skatītāji ir noguruši no drāmas un dotu priekšroku kaut kam vairāk romantiskam. Tāpēc tika nolemts sašaut tēlus ar mīlas bultām tā, lai visi tēli būtu attiecībās. Sašaujot kādu ar mīlas bultu, ir iespējams mainīt, ko tas tēls mīl (uz jebkuru tēlu pēc jūsu izvēles).

Kāds ir vismazākais nepieciešamais mīlas bultu skaits, lai visi tēli būtu attiecībās?

Ievaddati

Pirmā ievaddatu rinda satur veselu skaitli $N$ – iesaistīto tēlu skaits. Nākamās $N$ rindas katra satur ar tukšumzīmi atdalītus divus vārdus $s$ un $t$, kas nozīmē, ka tēls $s$ sākotnēji mīl tēlu $t$. Tēlu vārdi ir ne vairāk kā $10$ burtu gari un tie sastāv no mazajiem angļu valodas alfabēta burtiem.

Izvaddati

Izvadiet vienu veselu skaitli – vismazāko mīlas bultu skaitu, kas nepieciešams, lai visi tēli būtu attiecībās. Ja tas nav iespējams, izvadiet -1.

Ierobežojumi

Jūsu risinājums tiks testēts uz vairākām testu grupām, par katru no tām var iegūt punktus. Katra testu grupa satur vienu vai vairākus testus. Lai iegūtu punktus par testu grupu, jums ir pareizi jāatrisina visi testi šajā grupā. Jūsu beigu vērtējums par uzdevumu būs starp visiem iesūtījumiem lielākais.

Paraugu paskaidrojumi

Pirmais paraugs ir ilustrēts augstāk redzamajā attēlā. Attēla augšējā daļa parāda sākotnējo mīlas situāciju, kur bulta no $s$ uz $t$ nozīmē, ka $s$ sākotnēji mīl $t$, un rozā krāsa izceļ trīs tēlus, kas jāsašauj ar mīlas bultām, lai iegūtu unikālo optimālo risinājumu. Attēla apakšējā daļa parāda situāciju pēc mīlas bultu izšaušanas.

Otrajā paraugā, kas apmierina trešās grupas ierobežojumus, ir vairāki optimāli risinājumi. Viens no tiem ir sašaut a, b un d ar mīlas bultām un likt tiem attiecīgi iemīlēties b, a un c.

Trešajā paraugā ir mīlas trīsstūris, kur neatkarīgi no izšauto mīlas bultu skaita, kāds vienmēr nebūs attiecībās.

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