Problem A
Meilės daugiakampis

Muilo operose dažnai yra daug veikėjų ir jų tarpusavio santykiai būna painūs. Viename TV šou yra $N$ dalyvių. Kiekvienas dalyvis yra įsimylėjęs lygiai vieną dalyvį (gali būti įsimylėjęs ir save patį). Sakysime, kad du dalyviai yra užmezgę santykius, tada ir tik tada, kai jie vienas kitą įsimylėję.

Deja, tokia galimybė leidžia susidaryti sudėtingiems santykiams, kuriuos pavadinsime „meilės daugiakampiu“. Sakysime, kad 3 ar daugiau dalyvių priklauso „meilės daugiakampiui“, jei pirmasis įsimylėjo antrąjį, antrasis – trečiąjį, ir t.t., o paskutinysis įsimylėjo pirmąjį.

Pastarosios apklausos parodė, kad žiūrovai pavargo nuo tokių dramų ir norėtų ko nors romantiškesnio. Todėl buvo nuspręsta į kai kuriuos dalyvius paleisti meilės strėles taip, kad kiekvienas dalyvis būtų užmezgęs santykius. Iššaudami meilės strėlę į dalyvį, galite pakeisti jo įsimylėjimo objektą (į bet kurį jūsų pasirinktą).

Kokį mažiausią skaičių strėlių reiktų paleisti, kad visi dalyviai būtų užmezgę santykius?

Pradiniai duomenys

Pirmoje eilutėje pateiktas sveikasis skaičius $N$ – dalyvių skaičius. Tolesnėse $N$ eilučių yra po du tarpu atskirtus vardus $s$ ir $t$, reiškiančius, kad dalyvis $s$ pradiniu momentu įsimylėjęs dalyvį $t$. Dalyvių vardų ilgiai neviršija $10$ simbolių ir sudaryti iš mažųjų anglų k. abėcėlės raidžių.

Rezultatai

Išveskite vieną sveikąjį skaičių – mažiausią galimą meilės strėlių skaičių, kurias paleidus į dalyvius, visi dalyviai bus „užmezgę santykius“. Jei tai neįmanoma, išveskite $-1$.

Ribojimai

Jūsų sprendimas bus testuojamas su keliomis testų grupėmis, kiekviena kurių vertinama tam tikru skaičiumi taškų. Kiekvieną testų grupę sudarys keletas testų. Taškai už testų grupę skiriami tik jei įveikiate visus tos grupės testus.

Pavyzdžių paaiškinimai

Pirmasis pavyzdys pavaizduotas paveikslėlyje aukščiau. Viršutinėje dalyje pavaizduota pradinė situacija, kur strėlė, vedanti iš $s$ į $t$, reiškia, kad pradiniu momentu $s$ įsimylėjęs $t$. Rožinė spalva parodo tris dalyvius, į kuriuos reikia paleisti strėles, norint gauti vienintelį optimalų sprendinį. Apatinėje dalyje pavaizduota situacija iššovus strėles.

Antrajame pavyzdyje (kuris tenkina 3-čios grupės ribojimus) galimi keli optimalūs sprendiniai. Vienas jų yra paleisti strėles į a, b ir d, kad jie įsimylėtų atitinkamai b, a ir c.

Trečiajame pavyzdyje yra meilės trikampis. Nesvarbu kaip ir kiek strėlių iššautume, vis viena liks kažkas, kas nebus užmezgęs santykių.

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