Conosci l'azienda Just Ordinary Inventions? L'attività di questa azienda consiste nel creare "invenzioni del tutto ordinarie".

JOI-kun sta giocando all'ultimo gioco sviluppato da Just Ordinary Inventions.

Questo gioco prevede l'esplorazione di un sotterraneo composto da diverse stanze e diversi sentieri. Un sentiero collega due stanze distinte nel sotterraneo ed è percorribile in entrambe le direzioni. Per ogni coppia di stanze distinte c'è al massimo un sentiero che le collega, e non ci sono sentieri i cui due estremi siano la stessa stanza. Inoltre, è noto che qualsiasi coppia di stanze nel sotterraneo può essere raggiunta l'una dall'altra utilizzando un certo numero di sentieri. Ogni stanza è molto simile alle altre, e le stanze con lo stesso numero di sentieri uscenti non possono essere distinte l'una dall'altra semplicemente osservando l'aspetto della stanza.

In questo gioco, per facilitare l'esplorazione, ogni stanza è dotata di un marchio e di un piedistallo. I sentieri che escono da una stanza possono essere contati come 1°, 2°, ... sentiero in base al marchio. La struttura del sotterraneo non cambia durante il gioco. Pertanto, se ti sposti dalla stessa stanza utilizzando il sentiero con lo stesso numero, arriverai sempre nella stessa stanza. Il piedistallo è decorato con una gemma il cui colore può essere cambiato dal giocatore. Il colore della gemma è uno tra colore 1, colore 2, ..., colore $X$, e il colore della gemma in ogni stanza all'inizio del gioco è il colore 1. Il colore della gemma non cambierà a meno che il giocatore non intervenga su di essa.

JOI-kun si è reso conto che se la struttura di questo sotterraneo, ovvero il modo in cui le stanze sono collegate dai sentieri, fosse nota, questo gioco potrebbe essere completato facilmente. Tuttavia, per quanto JOI-kun ci abbia provato, non è riuscito a determinare la struttura del sotterraneo. Pertanto, hai deciso di scrivere un programma per determinare la struttura del sotterraneo per conto di JOI-kun.

Compito

Crea un programma che esplori il sotterraneo e ne determini la struttura. Tuttavia, poiché JOI-kun non voleva che la struttura del sotterraneo venisse completamente rivelata, il programma non deve rispondere direttamente con la struttura del sotterraneo, ma deve invece rispondere con il valore di "quante coppie di stanze ci sono che possono essere raggiunte utilizzando un minimo di esattamente $i$ sentieri" (le coppie in cui l'ordine delle stanze è scambiato sono considerate la stessa coppia) per ciascun intero $i$ da 1 a $R$.

Per esplorare il sotterraneo ti viene fornita una libreria che esegue le seguenti azioni:

• Sapere quanti sentieri escono dalla stanza attuale.
• Sapere il colore della gemma posta sul piedistallo nella stanza attuale.
• Cambiare il colore della gemma posta sul piedistallo nella stanza attuale in un colore specificato (è anche possibile specificare lo stesso colore di quello attuale). Successivamente, scegliere un sentiero che esce dalla stanza e spostarsi in un'altra stanza utilizzando quel sentiero.
• Sapere quale numero di sentiero era l'ultimo sentiero utilizzato tra quelli che escono dalla stanza attuale.

Dettagli di implementazione

Devi scrivere un singolo programma che implementi il metodo di risposta per JOI-kun. Il programma deve includere dungeon2.h.

Il programma deve implementare la seguente funzione:

• void Inspect(int R)
  • Questa funzione viene chiamata esattamente una volta all'inizio.
  • L'argomento $R$ indica che devi rispondere con il valore di "quante coppie di stanze ci sono che possono essere raggiunte utilizzando un minimo di esattamente $i$ sentieri" per ciascun intero $i$ da 1 a $R$.

Inoltre, devi chiamare la seguente funzione per rispondere alle domande:

• void Answer(int D, int A)
  • Gli argomenti $D$ e $A$ indicano che in questa chiamata stai rispondendo che "ci sono $A$ coppie di stanze che possono essere raggiunte utilizzando un minimo di esattamente $D$ sentieri".

Tuttavia, la chiamata ad Answer deve soddisfare le seguenti condizioni:

• $D$ deve essere un intero compreso tra 1 e $R$. Se ciò non è soddisfatto, verrà giudicato come Non corretto [1].
• Answer non deve essere chiamata più di una volta con lo stesso argomento $D$. Se ciò non è soddisfatto, verrà giudicato come Non corretto [2].
• Answer deve essere chiamata esattamente $R$ volte. Se ciò non è soddisfatto, verrà giudicato come Non corretto [3].
• $A$ deve essere il numero di coppie di stanze che possono essere raggiunte utilizzando un minimo di esattamente $D$ sentieri. Se ciò non è soddisfatto, verrà giudicato come Non corretto [4].

Se una chiamata ad Answer viene giudicata non corretta, il resto del programma potrebbe non essere eseguito.

Inoltre, nel tuo programma puoi chiamare le seguenti funzioni:

• void Move(int I, int C)
  • L'argomento $I$ è il numero del sentiero scelto dal giocatore per muoversi. Immediatamente dopo questa chiamata, il giocatore si sposta in un'altra stanza utilizzando l'$I$-esimo sentiero che esce dalla stanza attuale.
  • L'argomento $C$ indica che il colore della gemma posta sul piedistallo nella stanza attuale viene cambiato nel colore $C$ prima di spostarsi nella nuova stanza.

Tuttavia, la chiamata a Move deve soddisfare le seguenti condizioni:

• L'argomento $I$ deve essere un intero compreso tra 1 e $K$, dove $K$ è il numero di sentieri che escono dalla stanza in cui si trova attualmente il giocatore. Se ciò non è soddisfatto, verrà giudicato come Non corretto [5].
• L'argomento $C$ deve essere un intero compreso tra 1 e $X$, dove $X$ è il numero di tipi di colori delle gemme. Il valore di $X$ è determinato per ciascun sottoproblema. Se ciò non è soddisfatto, verrà giudicato come Non corretto [6].

• Move non deve essere chiamata più di 1,500,000 volte. Se viene chiamata di più, verrà giudicato come Non corretto [7].

• int NumberOfRoads()

  • Questa funzione restituisce il numero di sentieri che escono dalla stanza in cui si trova attualmente il giocatore.

• int LastRoad()

  • Questa funzione restituisce il numero dell'ultimo sentiero utilizzato tra quelli che escono dalla stanza attuale. Tuttavia, se questa funzione viene chiamata prima che Move venga chiamata anche solo una volta, restituisce -1.

• int Color()

  • Questa funzione restituisce il colore della gemma posta sul piedistallo nella stanza in cui si trova attualmente il giocatore.

Dopo il termine della chiamata alla funzione Inspect, la risposta viene valutata.

Sei libero di implementare altre funzioni per uso interno o di dichiarare variabili globali. Tuttavia, il codice inviato non deve interagire in alcun modo con lo standard input/standard output né con altri file.

Compilazione ed esecuzione

Un grader di esempio è fornito nell'archivio scaricabile dal sito della gara. Questo archivio contiene anche un esempio del file che devi inviare.

Il grader di esempio è costituito da un singolo file, grader.c o grader.cpp. Per testare il tuo programma, esegui i seguenti comandi:

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

Se la compilazione ha successo, viene generato un eseguibile chiamato grader.

Si noti che il grader effettivo utilizzato per la valutazione è diverso dal grader di esempio. Il grader di esempio viene eseguito come un singolo processo, leggendo i dati da standard input e scrivendo i risultati su standard output.

Input del grader di esempio

Il grader di esempio legge i seguenti dati da standard input:

• La 1ª riga contiene gli interi $N, X, R$ separati da uno spazio. Ciò indica che ci sono $N$ stanze nel sotterraneo: stanza 1, stanza 2, ..., stanza $N$, ci sono $X$ tipi di colori per le gemme e il programma deve rispondere con $R$ valori.
• Nelle successive $2N$ righe, la $(2i - 1)$-esima riga ($1 \le i \le N$) contiene un intero $D_i$, che indica che $D_i$ sentieri escono dalla stanza $i$. La $2i$-esima riga ($1 \le i \le N$) contiene $D_i$ interi $T_{i1}, T_{i2}, \dots, T_{iD_i}$ separati da spazi. Ciò indica che muovendosi lungo il $j$-esimo sentiero ($1 \le j \le D_i$) che esce dalla stanza $i$ si arriva alla stanza $T_{ij}$.
• Nelle successive $R$ righe, la $j$-esima riga ($1 \le j \le R$) contiene un intero $A_j$. Ciò indica che ci sono $A_j$ coppie di stanze che possono essere raggiunte utilizzando un minimo di esattamente $j$ sentieri. Ossia, per ciascun $j$ ($1 \le j \le R$), se Answer viene chiamata con l'argomento $D$ pari a $j$ e l'argomento $A$ pari a $A_j$, il grader di esempio la giudicherà corretta, altrimenti la giudicherà non corretta.

Il grader di esempio chiama la tua funzione con la posizione iniziale del giocatore nella stanza 1.

Output del grader di esempio

Quando l'esecuzione del programma termina normalmente, il grader di esempio stampa le seguenti informazioni su una riga su standard output (le virgolette non vengono effettivamente stampate):

• Se corretto, il numero di chiamate alla funzione Move viene stampato come Accepted : #move = 8.
• Se non corretto, il tipo di errore viene stampato come Wrong Answer [1].

Vincoli

Tutti i dati di input soddisfano le seguenti condizioni. Si faccia riferimento alla sezione 'Input del grader di esempio' per il significato di $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$ e $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$) sono tutti distinti.
• Per ciascuno $i, j$ ($1 \le i \le N, 1 \le j \le D_i$), esiste $k$ ($1 \le k \le D_{T_{ij}}$) tale che $T_{T_{ij}k} = i$.
• Qualsiasi coppia di stanze può essere raggiunta l'una dall'altra utilizzando un certo numero di sentieri.

Sottoproblemi

Nel seguito, siano $N$ il numero di stanze e $M$ il numero di sentieri nel sotterraneo nei dati di input.

Sottoproblema 1 [17 punti]

Sono soddisfatte le seguenti condizioni:

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

Sottoproblema 2 [27 punti]

Sono soddisfatte le seguenti condizioni:

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

Sottoproblema 3 [56 punti]

• Vale $X = 3$.

In questo sottoproblema, il punteggio è determinato come segue:

• Sia $L$ il valore massimo della seguente quantità su tutti i casi di prova di questo sottoproblema:
  • $\frac{C}{M}$, dove $C$ è il numero di chiamate a Move.
• In tal caso, il punteggio per questo sottoproblema è:
  • Se $L \le 14$, 56 punti.
  • Se $14 < L \le 32$, $\lfloor 70 - L \rfloor$ punti.
  • Se $32 < L \le 64$, $\lfloor 54 - \frac{L}{2} \rfloor$ punti.
  • Se $64 < L$, 0 punti.

Qui, $\lfloor x \rfloor$ rappresenta il più grande intero che non supera $x$.

Esempi

Input 1

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

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

Nota

Le chiamate di funzione in questo esempio non sono necessariamente chiamate significative.