Kjenner du til selskapet Just Ordinary Inventions? Virksomheten til dette selskapet går ut på å lage «helt vanlige oppfinnelser».

JOI-kun spiller det nyeste spillet utviklet av Just Ordinary Inventions.

Dette spillet går ut på å utforske et fangehull som består av flere rom og flere stier. En sti forbinder to forskjellige rom i fangehullet og kan brukes i begge retninger. For ethvert par av forskjellige rom er det høyst én sti som forbinder dem, og det finnes ingen stier der begge endene er det samme rommet. Videre er det kjent at man kan komme seg mellom hvilke som helst to rom i fangehullet ved å bruke et visst antall stier. Hvert rom er svært likt de andre, og rom med samme antall utgående stier kan ikke skilles fra hverandre bare ved å se på utseendet til rommet.

I dette spillet er hvert rom utstyrt med et merke og en pidestall for å hjelpe til med utforskningen. Stiene som fører ut fra et rom, kan telles som den 1., 2., ... stien basert på merket. Strukturen til fangehullet endrer seg ikke i løpet av spillet. Hvis du beveger deg fra det samme rommet ved å bruke stien med det samme nummeret, vil du derfor alltid komme til det samme rommet. Pidestallen er dekorert med én edelsten hvis farge kan endres av spilleren. Fargen på edelstenen er én av farge 1, farge 2, ..., farge $X$, og fargen på edelstenen i hvert rom ved starten av spillet er farge 1. Fargen på edelstenen endres ikke med mindre spilleren endrer den.

JOI-kun innså at dersom strukturen til dette fangehullet, det vil si hvordan rommene er forbundet med stier, var kjent, kunne dette spillet enkelt rundes. Men uansett hvor mye JOI-kun prøvde, klarte han ikke å finne ut strukturen til fangehullet. Derfor har du bestemt deg for å skrive et program for å bestemme strukturen til fangehullet på vegne av JOI-kun.

Oppgave

Lag et program som utforsker fangehullet og bestemmer strukturen. Siden JOI-kun ikke ønsket at strukturen til fangehullet skulle avsløres fullstendig, må programmet imidlertid ikke svare med strukturen til fangehullet direkte, men i stedet svare med verdien av «hvor mange par av rom som finnes som kan nås ved bruk av et minimum på nøyaktig $i$ stier» (par der rekkefølgen på rommene er byttet om, regnes som det samme paret) for hvert heltall $i$ fra 1 til $R$.

For å utforske fangehullet får du utdelt et bibliotek som utfører følgende handlinger:

• Få vite hvor mange stier som fører ut fra det nåværende rommet.
• Få vite fargen på edelstenen som står på pidestallen i det nåværende rommet.
• Endre fargen på edelstenen på pidestallen i det nåværende rommet til en oppgitt farge (du kan også oppgi samme farge som den nåværende). Velg deretter én sti som fører ut fra rommet, og flytt til et annet rom ved hjelp av den stien.
• Få vite hvilket nummer den sist brukte stien hadde blant stiene som fører ut fra det nåværende rommet.

Implementasjonsdetaljer

Du må skrive ett program som implementerer metoden for at JOI-kun skal svare. Programmet må inkludere dungeon2.h.

Programmet må implementere følgende rutine:

• void Inspect(int R)
  • Denne rutinen kalles nøyaktig én gang i starten.
  • Argumentet $R$ angir at du må svare med verdien av «hvor mange par av rom som finnes som kan nås ved bruk av et minimum på nøyaktig $i$ stier» for hvert heltall $i$ fra 1 til $R$.

I tillegg må du kalle følgende rutine for å svare på spørsmålene:

• void Answer(int D, int A)
  • Argumentene $D$ og $A$ angir at du i dette kallet svarer at «det finnes $A$ par av rom som kan nås ved bruk av et minimum på nøyaktig $D$ stier».

Kallet til Answer må imidlertid oppfylle følgende betingelser:

• $D$ må være et heltall mellom 1 og $R$. Hvis dette ikke er oppfylt, blir det bedømt som Feil [1].
• Answer må ikke kalles mer enn én gang med samme argument $D$. Hvis dette ikke er oppfylt, blir det bedømt som Feil [2].
• Answer må kalles nøyaktig $R$ ganger. Hvis dette ikke er oppfylt, blir det bedømt som Feil [3].
• $A$ må være antallet par av rom som kan nås ved bruk av et minimum på nøyaktig $D$ stier. Hvis dette ikke er oppfylt, blir det bedømt som Feil [4].

Hvis et kall til Answer blir bedømt som feil, vil resten av programmet kanskje ikke bli kjørt.

I tillegg kan du kalle følgende rutiner i programmet ditt:

• void Move(int I, int C)
  • Argumentet $I$ er nummeret på stien spilleren velger å følge. Umiddelbart etter dette kallet flytter spilleren til et annet rom ved hjelp av den $I$-te stien som fører ut fra det nåværende rommet.
  • Argumentet $C$ angir at fargen på edelstenen på pidestallen i det nåværende rommet endres til farge $C$ før spilleren flytter til det nye rommet.

Kallet til Move må imidlertid oppfylle følgende betingelser:

• Argumentet $I$ må være et heltall mellom 1 og $K$, der $K$ er antallet stier som fører ut fra rommet der spilleren befinner seg nå. Hvis dette ikke er oppfylt, blir det bedømt som Feil [5].
• Argumentet $C$ må være et heltall mellom 1 og $X$, der $X$ er antallet typer edelstensfarger. Verdien av $X$ er bestemt for hver deloppgave. Hvis dette ikke er oppfylt, blir det bedømt som Feil [6].

• Move må ikke kalles mer enn 1,500,000 ganger. Hvis den kalles flere ganger, blir det bedømt som Feil [7].

• int NumberOfRoads()

  • Denne funksjonen returnerer antallet stier som fører ut fra rommet der spilleren befinner seg nå.

• int LastRoad()

  • Denne funksjonen returnerer hvilket nummer den sist brukte stien hadde blant stiene som fører ut fra det nåværende rommet. Hvis denne funksjonen kalles før Move har blitt kalt én eneste gang, returnerer den imidlertid -1.

• int Color()

  • Denne funksjonen returnerer fargen på edelstenen på pidestallen i rommet der spilleren befinner seg nå.

Etter at rutinen Inspect er kalt, blir svaret bedømt.

Du står fritt til å implementere andre rutiner til internt bruk eller deklarere globale variabler. Innleveringen din må imidlertid ikke interagere med standard inndata/standard utdata eller andre filer på noen som helst måte.

Kompilering og kjøring

En eksempelbedømmer (sample grader) følger med i arkivet som kan lastes ned fra konkurransesiden. Dette arkivet inneholder også et eksempel på filen du må sende inn.

Eksempelbedømmeren består av én enkelt fil, grader.c eller grader.cpp. For å teste programmet ditt, kjør følgende kommandoer:

• For C: gcc -std=c11 -O2 -o grader grader.c dungeon2.c -lm
• For C++: g++ -std=c++11 -O2 -o grader grader.cpp dungeon2.cpp

Hvis kompileringen er vellykket, genereres en kjørbar fil med navnet grader.

Merk at den faktiske bedømmeren som brukes under evalueringen, er forskjellig fra eksempelbedømmeren. Eksempelbedømmeren kjører som én enkelt prosess som leser inndata fra standard inndata og skriver resultater til standard utdata.

Inndata for eksempelbedømmeren

Eksempelbedømmeren leser følgende data fra standard inndata:

• Den 1. linjen inneholder heltallene $N, X, R$ adskilt med mellomrom. Dette representerer at det er $N$ rom i fangehullet: rom 1, rom 2, ..., rom $N$, at det er $X$ typer edelstensfarger, og at programmet må svare med $R$ verdier.
• I de påfølgende $2N$ linjene inneholder den $(2i - 1)$-te linjen ($1 \le i \le N$) et heltall $D_i$, som representerer at $D_i$ stier fører ut fra rom $i$. Den $2i$-te linjen ($1 \le i \le N$) inneholder $D_i$ heltall $T_{i1}, T_{i2}, \dots, T_{iD_i}$ adskilt med mellomrom. Dette representerer at hvis man beveger seg langs den $j$-te stien ($1 \le j \le D_i$) som fører ut fra rom $i$, kommer man til rom $T_{ij}$.
• I de påfølgende $R$ linjene inneholder den $j$-te linjen ($1 \le j \le R$) et heltall $A_j$. Dette representerer at det er $A_j$ par av rom som kan nås ved bruk av et minimum på nøyaktig $j$ stier. Det vil si at for hver $j$ ($1 \le j \le R$), hvis Answer kalles med argumentet $D$ lik $j$ og argumentet $A$ lik $A_j$, vil eksempelbedømmeren bedømme det som riktig, og ellers som feil.

Eksempelbedømmeren kaller rutinen din med spillerens startposisjon i rom 1.

Utdata fra eksempelbedømmeren

Når programkjøringen avsluttes normalt, skriver eksempelbedømmeren ut følgende informasjon på én linje til standard utdata (anførselstegn skrives ikke faktisk ut):

• Hvis svaret er riktig, skrives antallet kall til funksjonen Move ut som Accepted : #move = 8.
• Hvis svaret er feil, skrives typen feil ut som Wrong Answer [1].

Begrensninger

Alle inndata oppfyller følgende betingelser. Se delen 'Inndata for eksempelbedømmeren' for betydningen av $N, D_i, T_{ij}$.

• $2 \le N \le 200$
• $3 \le X \le 100$
• $1 \le R \le 200$
• $1 \le D_i \le N - 1$ ($1 \le i \le N$)
• $1 \le T_{ij} \le N$ og $T_{ij} \neq i$ ($1 \le i \le N, 1 \le j \le D_i$)
• $T_{i1}, T_{i2}, \dots, T_{iD_i}$ ($1 \le i \le N$) er forskjellige.
• For hver $i, j$ ($1 \le i \le N, 1 \le j \le D_i$) finnes det en $k$ ($1 \le k \le D_{T_{ij}}$) slik at $T_{T_{ij}k} = i$.
• Hvilke som helst to rom kan nås fra hverandre ved å bruke et visst antall stier.

Deloppgaver

I det følgende lar vi $N$ være antallet rom og $M$ være antallet stier i fangehullet i inndataene.

Deloppgave 1 [17 poeng]

Følgende betingelser er oppfylt:

• $N \le 50$
• $M \le 100$
• $X = 100$

Deloppgave 2 [27 poeng]

Følgende betingelser er oppfylt:

• $N \le 50$
• $M \le 100$
• $X = 3$

Deloppgave 3 [56 poeng]

• $X = 3$ er oppfylt.

I denne deloppgaven bestemmes poengsummen på følgende måte:

• La $L$ være den største verdien av følgende for alle testtilfellene i denne deloppgaven:
  • $\frac{C}{M}$, der $C$ er antallet kall til Move.
• I dette tilfellet er poengsummen for denne deloppgaven:
  • Hvis $L \le 14$, 56 poeng.
  • Hvis $14 < L \le 32$, $\lfloor 70 - L \rfloor$ poeng.
  • Hvis $32 < L \le 64$, $\lfloor 54 - \frac{L}{2} \rfloor$ poeng.
  • Hvis $64 < L$, 0 poeng.

Her representerer $\lfloor x \rfloor$ det største heltallet som ikke overstiger $x$.

Eksempler

Inndata 1

4 3 3
1
2
3
1 3 4
2
2 4
2
2 3
4
2
0

Utdata 1

Inspect(3)
NumberOfRoads() -> 1
LastRoad() -> -1
Move(1,2)
Color() -> 1
LastRoad() -> 1
NumberOfRoads() -> 3
Move(1,3)
Color() -> 2
Answer(1,4)
Answer(2,2)
Answer(3,0)

Forklaring

Funksjonskallene i dette eksempelet er ikke nødvendigvis meningsfulle kall.