Problem G
Cirkelmeme
Det er gyldigt både i eksempelindlæsning 1 og 2.
Chris har lavet et cirkelmeme og lagt det op på nettet for at høste internetpoint.
Fænomenet stammer fra amerikanske collegesportsligaer og e-sport og går ud på at lave sjov med resultatet af de kampe, der er spillet i en sæson. Når et hold vinder over et andet, må det være fordi det første hold er dygtigere, men i praksis fungerer dette rationale ikke. Hvis hold A vinder over hold B, hold B vinder over hold C, og hold C til sidst vinder over hold A, så bliver det svært at forsvare, at hold A er bedre end hold B, i hvert fald alene ud fra resultatet af kampene. I stedet kan man konkludere, at holdene må være lige dygtige (eller lige dårlige). Et cirkelmeme konstrueres ved at finde en følge af hold $a_1$, $a_2$, $\ldots $, $a_ k$, hvor hold $a_ i$ har vundet over hold $a_{i+1}$ (for alle $i < k$), og hold $a_ k$ har vundet over hold $a_1$. Holdenes logoer illustreres med forsæt udueligt i en cirkel og forbindes med pile.
Chris er ikke helt tilfreds men den mængde internetpoint, han har indkasseret. Måske havde folk været mere begejstrede for hans kreation, hvis han havde været tidligere ude. Måske burde han have lagt billedet op straks efter afslutningen af den kamp, der fuldendte cirklen?
Indlæsning
Indlæsningens første linje består af at et heltal $N$, der angiver antallet af kampe, der er blevet spillet i sæsonen.
Derefter følger $N$ linjer, der beskriver sæsonens kampe i kronologisk rækkefølge. Resultatet af en kamp er beskrevet med to forskellige holdnavne $A$ og $B$, adskilte af mellemrum, og skal forstås således, at hold $A$ vandt over hold $B$. Holdnavnene består af højst $10$ store og små engelske bogstaver (a-z og A-Z).
To hold vil aldrig have spillet mod hinanden mere end én gang, men forskellige hold kan godt ende med at have spillet et forskelligt antal kampe.
Indlæsningen garanterer, at et gyldigt cirkelmeme kan konstrueres senest ved sæsonens afslutning.
Udskrift
Udskriv det mindste heltal $M$, for hvilket Chris vil kunne konstruere et gyldigt cirkelmeme ud fra sæsonens første $M$ kampe. Der gælder $3 \leq M \leq N$.
Garantier og delopgaver
Der gælder altid $3 \leq N \leq 10^5$.
Opgaven er opdelt i delopgaver med stærkere garantier, som gør delopgaven nemmere at løse.
|
Delopgave |
Point |
Garanti |
|
$1$ |
$20$ |
$N \leq 8$ |
|
$2$ |
$38$ |
$N \leq 5000$ |
|
$3$ |
$42$ |
$N \leq 10^5$ |
| Sample Input 1 | Sample Output 1 |
|---|---|
6 OB FCK FCK FCN AGF FCK OB AaB FCN BIF BIF OB |
6 |
| Sample Input 2 | Sample Output 2 |
|---|---|
8 BIF OB FCK FCN BIF AaB AaB OB FCN BIF FCK VFF OB FCK VFF AaB |
7 |
| Sample Input 3 | Sample Output 3 |
|---|---|
5 AGF BIF AGF FCN BIF FCN OB AGF BIF OB |
5 |
