Problem A
Mīlas daudzstūris
Languages
de
en
et
is
ja
lt
lv
no
pl
ru
sv
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.
|
Grupa |
Punkti |
Ierobežojumi |
Papildu ierobežojumi |
|
1 |
21 |
$2 \le N \le 20$ |
|
|
2 |
25 |
$2 \le N \le 100\, 000$ |
Katru tēlu kāds mīl (iespējams, viņš pats). |
|
3 |
29 |
$2 \le N \le 100\, 000$ |
Sākotnēji nav nekādu attiecību vai “mīlas daudzstūru”. |
|
4 |
25 |
$2 \le N \le 100\, 000$ |
Paraugu paskaidrojumi
![\includegraphics[width=0.5\textwidth ]{polygonfig.pdf}](/problems/lovepolygon/file/statement/lv/img-0001.png)
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.
| Ievaddatu paraugs 1 | Izvaddatu paraugs 1 |
|---|---|
8 leonard emmy ada emmy isaac leonard emmy pierre pierre bernhard bernhard emmy sofia karl karl sofia |
3 |
| Ievaddatu paraugs 2 | Izvaddatu paraugs 2 |
|---|---|
4 a c b c c d d d |
3 |
| Ievaddatu paraugs 3 | Izvaddatu paraugs 3 |
|---|---|
3 rocky scarlet scarlet patrick patrick rocky |
-1 |
