Känner du till företaget Just Ordinary Inventions? Detta företags affärsidé är att skapa "helt vanliga uppfinningar".

JOI-kun spelar det senaste spelet som utvecklats av Just Ordinary Inventions.

Detta spel går ut på att utforska en fängelsehåla som består av flera rum och flera gångar. En gång förbinder två skilda rum i fängelsehålan och kan beträdas i båda riktningarna. För varje par av skilda rum finns det högst en gång som förbinder dem, och det finns inga gångar där båda ändarna är samma rum. Vidare är det känt att man kan ta sig mellan vilka två rum som helst i fängelsehålan genom att använda något antal gångar. Varje rum är mycket likt de andra, och rum med samma antal utgående gångar kan inte skiljas från varandra bara genom att titta på rummets utseende.

I detta spel är varje rum utrustat med ett märke och en piedestal för att underlätta utforskandet. Gångarna som leder ut från ett rum kan räknas som den 1:a, 2:a, ... gången utgående från märket. Fängelsehålans struktur ändras inte under spelets gång. Om du förflyttar dig från samma rum via gången med samma nummer kommer du därför alltid till samma rum. Piedestalen är prydd med en ädelsten vars färg kan ändras av spelaren. Ädelstenens färg är en av färg 1, färg 2, ..., färg $X$, och vid spelets start har ädelstenen i varje rum färg 1. Ädelstenens färg ändras inte såvida inte spelaren ändrar den.

JOI-kun insåg att om strukturen hos denna fängelsehåla, det vill säga hur rummen är förbundna med gångar, vore känd, skulle spelet enkelt kunna klaras av. Men hur mycket JOI-kun än försökte kunde han inte bestämma fängelsehålans struktur. Därför har du bestämt dig för att skriva ett program som bestämmer fängelsehålans struktur åt JOI-kun.

Uppgift

Skapa ett program som utforskar fängelsehålan och bestämmer dess struktur. Eftersom JOI-kun inte ville att fängelsehålans struktur skulle avslöjas helt och hållet får programmet dock inte svara med fängelsehålans struktur direkt, utan måste istället svara med värdet på "hur många par av rum det finns som kan nås från varandra med ett minimum av exakt $i$ gångar" (par där ordningen på rummen är omvänd räknas som samma par) för varje heltal $i$ från 1 till $R$.

För att utforska fängelsehålan får du tillgång till ett bibliotek som utför följande åtgärder:

• Ta reda på hur många gångar som leder ut från det nuvarande rummet.
• Ta reda på färgen på ädelstenen på piedestalen i det nuvarande rummet.
• Ändra färgen på ädelstenen på piedestalen i det nuvarande rummet till en angiven färg (du kan också ange samma färg som den nuvarande). Välj därefter en gång som leder ut från rummet och gå till ett annat rum via den gången.
• Ta reda på vilket nummer den senast använda gången hade bland de gångar som leder ut från det nuvarande rummet.

Implementeringsdetaljer

Du måste skriva ett program som implementerar metoden för JOI-kun att svara. Programmet måste inkludera dungeon2.h.

Programmet måste implementera följande rutin:

• void Inspect(int R)
  • Denna rutin anropas exakt en gång i början.
  • Argumentet $R$ anger att du måste svara med värdet på "hur många par av rum det finns som kan nås med ett minimum av exakt $i$ gångar" för varje heltal $i$ från 1 till $R$.

Du måste också anropa följande rutin för att svara på frågorna:

• void Answer(int D, int A)
  • Argumenten $D$ och $A$ anger att du i detta anrop svarar att "det finns $A$ par av rum som kan nås med ett minimum av exakt $D$ gångar".

Anropet till Answer måste dock uppfylla följande villkor:

• $D$ måste vara ett heltal mellan 1 och $R$. Om detta inte uppfylls bedöms det som Felaktigt [1].
• Answer får inte anropas mer än en gång med samma argument $D$. Om detta inte uppfylls bedöms det som Felaktigt [2].
• Answer måste anropas exakt $R$ gånger. Om detta inte uppfylls bedöms det som Felaktigt [3].
• $A$ måste vara antalet par av rum som kan nås med ett minimum av exakt $D$ gångar. Om detta inte uppfylls bedöms det som Felaktigt [4].

Om ett anrop till Answer bedöms som felaktigt är det inte säkert att resten av programmet körs.

Dessutom kan du anropa följande rutiner i ditt program:

• void Move(int I, int C)
  • Argumentet $I$ är numret på den gång som spelaren väljer att gå genom. Omedelbart efter detta anrop går spelaren till ett annat rum via den $I$-te gången som leder ut från det nuvarande rummet.
  • Argumentet $C$ anger att färgen på ädelstenen på piedestalen i det nuvarande rummet ändras till färg $C$ innan spelaren går vidare till nästa rum.

Anropet till Move måste dock uppfylla följande villkor:

• Argumentet $I$ måste vara ett heltal mellan 1 och $K$, där $K$ är antalet gångar som leder ut från rummet där spelaren befinner sig för tillfället. Om detta inte uppfylls bedöms det som Felaktigt [5].
• Argumentet $C$ måste vara ett heltal mellan 1 och $X$, där $X$ är antalet typer av ädelstensfärger. Värdet på $X$ är bestämt för varje deluppgift. Om detta inte uppfylls bedöms det som Felaktigt [6].

• Move får inte anropas mer än 1,500,000 gånger. Om den anropas fler gånger bedöms det som Felaktigt [7].

• int NumberOfRoads()

  • Denna funktion returnerar antalet gångar som leder ut från rummet där spelaren befinner sig för tillfället.

• int LastRoad()

  • Denna funktion returnerar vilket nummer den senast använda gången hade bland de gångar som leder ut från det nuvarande rummet. Om denna funktion anropas innan Move har anropats ens en gång returnerar den dock -1.

• int Color()

  • Denna funktion returnerar färgen på ädelstenen på piedestalen i rummet där spelaren befinner sig för tillfället.

Efter att rutinen Inspect har anropats bedöms svaret.

Det står dig fritt att implementera andra rutiner för internt bruk eller att deklarera globala variabler. Ditt inskickade program får dock inte interagera med standard inmatning/standard utmatning eller några andra filer på något sätt.

Kompilering och körning

En exempelbedömare (sample grader) finns i arkivet som kan laddas ner från tävlingssidan. Detta arkiv innehåller också ett exempel på filen som du ska skicka in.

Exempelbedömaren består av en enda fil, grader.c eller grader.cpp. För att testa ditt program, kör följande kommandon:

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

Om kompileringen lyckas skapas en körbar fil med namnet grader.

Observera att den faktiska bedömaren som används vid utvärderingen skiljer sig från exempelbedömaren. Exempelbedömaren körs som en enda process som läser indata från standard inmatning och skriver resultat till standard utmatning.

Indata för exempelbedömaren

Exempelbedömaren läser följande data från standard inmatning:

• Den 1:a raden innehåller heltalen $N, X, R$ åtskilda av mellanslag. Detta anger att det finns $N$ rum i fängelsehålan: rum 1, rum 2, ..., rum $N$, att det finns $X$ typer av ädelstensfärger och att programmet måste svara med $R$ värden.
• På de följande $2N$ raderna innehåller den $(2i - 1)$-te raden ($1 \le i \le N$) ett heltal $D_i$, som anger att $D_i$ gångar leder ut från rum $i$. Den $2i$-te raden ($1 \le i \le N$) innehåller $D_i$ heltal $T_{i1}, T_{i2}, \dots, T_{iD_i}$ åtskilda av mellanslag. Detta anger att om man går längs den $j$-te gången ($1 \le j \le D_i$) som leder ut från rum $i$ kommer man till rum $T_{ij}$.
• På de följande $R$ raderna innehåller den $j$-te raden ($1 \le j \le R$) ett heltal $A_j$. Detta anger att det finns $A_j$ par av rum som kan nås med ett minimum av exakt $j$ gångar. Det vill säga, om Answer för varje $j$ ($1 \le j \le R$) anropas med argumentet $D$ som $j$ och argumentet $A$ som $A_j$ kommer exempelbedömaren att bedöma det som rätt, och annars som fel.

Exempelbedömaren anropar din rutin med spelarens startposition i rum 1.

Utdata från exempelbedömaren

När programkörningen avslutas normalt skriver exempelbedömaren ut följande information på en rad till standard utmatning (citattecken skrivs inte ut i verkligheten):

• Om allt är rätt skrivs antalet anrop till funktionen Move ut som Accepted : #move = 8.
• Om något är fel skrivs typen av fel ut som Wrong Answer [1].

Begränsningar

All indata uppfyller följande villkor. Se avsnittet 'Indata för exempelbedömaren' för betydelsen 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$ och $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$) är alla olika.
• För varje $i, j$ ($1 \le i \le N, 1 \le j \le D_i$) finns det ett $k$ ($1 \le k \le D_{T_{ij}}$) sådant att $T_{T_{ij}k} = i$.
• Vilka två rum som helst kan nås från varandra genom att använda något antal gångar.

Deluppgifter

Låt i det följande $N$ vara antalet rum och $M$ vara antalet gångar i fängelsehålan i indatan.

Deluppgift 1 [17 poäng]

Följande villkor är uppfyllda:

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

Deluppgift 2 [27 poäng]

Följande villkor är uppfyllda:

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

Deluppgift 3 [56 poäng]

• $X = 3$ är uppfyllt.

I denna deluppgift bestäms poängen enligt följande:

• Låt $L$ vara det största värdet av följande över alla testfall i denna deluppgift:
  • $\frac{C}{M}$, där $C$ är antalet anrop till Move.
• Då är poängen för denna deluppgift:
  • Om $L \le 14$, 56 poäng.
  • Om $14 < L \le 32$, $\lfloor 70 - L \rfloor$ poäng.
  • Om $32 < L \le 64$, $\lfloor 54 - \frac{L}{2} \rfloor$ poäng.
  • Om $64 < L$, 0 poäng.

Här betecknar $\lfloor x \rfloor$ det största heltalet som inte överstiger $x$.

Exempel

Indata 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)

Förklaring

Funktionsanropen i detta exempel är inte nödvändigtvis meningsfulla anrop.