Kennst du die Firma Just Ordinary Inventions? Ihre Tätigkeit besteht darin, „einfach gewöhnliche Erfindungen“ zu machen.

JOI spielt das neueste Spiel, das von Just Ordinary Inventions entwickelt wurde.

In diesem Spiel erkundet man einen Dungeon aus mehreren Räumen und Wegen. Jeder Weg verbindet zwei verschiedene Räume und kann in beiden Richtungen durchlaufen werden. Zwischen zwei verschiedenen Räumen gibt es höchstens einen Weg; Wege, deren beide Enden im selben Raum liegen, gibt es nicht. Außerdem kann man zwischen beliebigen zwei Räumen des Dungeons über einige Wege gelangen. Die Räume sehen einander sehr ähnlich: Räume mit derselben Anzahl ausgehender Wege lassen sich allein anhand ihres Aussehens überhaupt nicht unterscheiden.

Zur Unterstützung gibt es in jedem Raum eine Markierung und einen Sockel. Ausgehend von der Markierung lassen sich die Wege eines Raums als erster, zweiter, … Weg zählen. Die Struktur des Dungeons ändert sich während des Spiels nicht. Wer aus demselben Raum denselben nummerierten Weg benutzt, gelangt daher immer in denselben Raum. Auf dem Sockel liegt ein Edelstein, dessen Farbe der Spieler ändern kann. Die Farbe ist eine der Farben $1,2,\ldots,X$. Zu Spielbeginn haben die Edelsteine aller Räume die Farbe $1$. Ohne eine Aktion des Spielers ändert sich die Farbe eines Edelsteins nicht.

JOI hat bemerkt, dass sich das Spiel leicht lösen ließe, wenn er die Struktur des Dungeons kennen würde, also wüsste, wie die Räume durch Wege verbunden sind. Trotz verschiedener Versuche konnte er die Struktur jedoch nicht bestimmen. Deshalb hast du beschlossen, für JOI ein Programm zu schreiben, das die Struktur des Dungeons bestimmt.

Aufgabe

Schreibe ein Programm, das den Dungeon erkundet und seine Struktur bestimmt. JOI möchte allerdings nicht die vollständige Struktur erfahren. Deshalb muss das Programm anstelle der Struktur selbst für jede ganze Zahl $i$ von $1$ bis $R$ angeben, wie viele Paare von Räumen es gibt, zwischen denen man mindestens genau $i$ Wege durchlaufen muss. Die Reihenfolge der beiden Räume spielt bei einem Paar keine Rolle.

Zum Erkunden des Dungeons steht dir eine Bibliothek für die folgenden Aktionen zur Verfügung.

• Die Anzahl der Wege ermitteln, die aus dem aktuellen Raum führen.
• Die Farbe des Edelsteins auf dem Sockel im aktuellen Raum ermitteln.
• Die Farbe des Edelsteins auf dem Sockel im aktuellen Raum auf eine angegebene Farbe setzen; die bisherige Farbe darf ebenfalls angegeben werden. Anschließend einen Weg aus diesem Raum auswählen und über ihn in einen anderen Raum gehen.
• Ermitteln, welche Nummer der zuletzt benutzte Weg unter den aus dem aktuellen Raum führenden Wegen hat.

Implementierungsdetails

Du musst ein Programm schreiben, das die Beantwortung der Fragen von JOI implementiert. Das Programm muss dungeon2.h einbinden.

Das Programm muss die folgende Routine implementieren.

• void Inspect(int R)

  Diese Routine wird zu Beginn genau einmal aufgerufen.

  • Der Parameter R gibt an, dass du für jede ganze Zahl $i$ von $1$ bis $R$ angeben musst, wie viele Paare von Räumen mindestens genau $i$ Wege voneinander entfernt sind. Das Vertauschen der Räume ergibt dasselbe Paar.

Außerdem musst du die folgende Routine aufrufen, um die Fragen zu beantworten.

• void Answer(int D, int A)

  • Mit den Parametern D und A gibt dieser Aufruf an, dass es $A$ Paare von Räumen gibt, zwischen denen mindestens genau $D$ Wege durchlaufen werden müssen.

  Die Aufrufe von Answer müssen folgende Bedingungen erfüllen.

  • D muss eine ganze Zahl zwischen $1$ und $R$ einschließlich sein. Andernfalls lautet das Urteil Falsche Antwort [1].
  • Answer darf nicht zweimal oder öfter mit demselben Parameter D aufgerufen werden. Andernfalls lautet das Urteil Falsche Antwort [2].
  • Answer muss genau $R$-mal aufgerufen werden. Andernfalls lautet das Urteil Falsche Antwort [3].
  • A muss die Anzahl der Raumpaare sein, zwischen denen mindestens genau $D$ Wege durchlaufen werden müssen. Andernfalls lautet das Urteil Falsche Antwort [4].

  Wenn ein Aufruf von Answer als falsch bewertet wird, ist nicht garantiert, dass das Programm anschließend weiter ausgeführt wird.

Zusätzlich darf das Programm die folgenden Routinen aufrufen.

• void Move(int I, int C)

  • Der Parameter I ist die Nummer des Weges, den der Spieler für seine Bewegung auswählt. Unmittelbar nach diesem Aufruf geht der Spieler über den $I$-ten Weg aus dem aktuellen Raum in einen anderen Raum.
  • Der Parameter C gibt an, dass vor der Bewegung die Farbe des Edelsteins auf dem Sockel des aktuellen Raums auf die Farbe $C$ gesetzt wird.

  Die Aufrufe von Move müssen folgende Bedingungen erfüllen.

  • Ist $K$ die Anzahl der Wege aus dem aktuellen Raum, muss I eine ganze Zahl zwischen $1$ und $K$ einschließlich sein. Andernfalls lautet das Urteil Falsche Antwort [5].
  • Gibt es $X$ Edelsteinfarben, muss C eine ganze Zahl zwischen $1$ und $X$ einschließlich sein. Der Wert von $X$ wird durch die jeweilige Teilaufgabe festgelegt. Andernfalls lautet das Urteil Falsche Antwort [6].
  • Move darf nicht öfter als $1\,500\,000$-mal aufgerufen werden. Andernfalls lautet das Urteil Falsche Antwort [7].

• int NumberOfRoads()

  • Diese Funktion gibt die Anzahl der Wege zurück, die aus dem aktuellen Raum des Spielers führen.

• int LastRoad()

  • Diese Funktion gibt die Nummer des zuletzt benutzten Weges unter den aus dem aktuellen Raum führenden Wegen zurück. Wird sie vor dem ersten Aufruf von Move aufgerufen, gibt sie jedoch $-1$ zurück.

• int Color()

  • Diese Funktion gibt die Farbe des Edelsteins auf dem Sockel im aktuellen Raum des Spielers zurück.

Nach dem Aufruf der Routine Inspect werden die Antworten bewertet.

Du darfst weitere Routinen für interne Zwecke implementieren und globale Variablen deklarieren. Deine Einreichung darf jedoch auf keinerlei Weise mit der Standardeingabe, der Standardausgabe oder anderen Dateien kommunizieren.

Kompilieren und Ausführen

Ein Archiv auf der Wettbewerbswebsite enthält einen Beispielgrader zum Testen deines Programms. Dieses Archiv enthält auch Beispiele der einzureichenden Dateien.

Der Beispielgrader besteht aus einer Datei namens grader.c oder grader.cpp. Um dein Programm zu testen, führe die folgenden Befehle aus.

• 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

Bei erfolgreicher Kompilierung wird eine ausführbare Datei namens grader erzeugt.

Beachte, dass der tatsächliche Grader vom Beispielgrader abweicht. Der Beispielgrader startet als einzelner Prozess, liest die Eingabe von der Standardeingabe und schreibt das Ergebnis auf die Standardausgabe.

Eingabe des Beispielgraders

Der Beispielgrader liest die folgenden Daten von der Standardeingabe.

• Die erste Zeile enthält die durch Leerzeichen getrennten ganzen Zahlen $N,X,R$. Das bedeutet, dass der Dungeon $N$ Räume mit den Nummern $1,2,\ldots,N$ hat, es $X$ Edelsteinfarben gibt und das Programm $R$ Werte angeben muss.
• In den folgenden $2N$ Zeilen enthält die $(2i-1)$-te Zeile ($1 \le i \le N$) die ganze Zahl $D_i$, die angibt, dass $D_i$ Wege aus Raum $i$ führen. Die $2i$-te Zeile ($1 \le i \le N$) enthält $D_i$ durch Leerzeichen getrennte ganze Zahlen $T_{i1},T_{i2},\ldots,T_{iD_i}$. Wer den $j$-ten Weg ($1 \le j \le D_i$) aus Raum $i$ benutzt, gelangt in Raum $T_{ij}$.
• Die $j$-te Zeile ($1 \le j \le R$) der folgenden $R$ Zeilen enthält die ganze Zahl $A_j$. Sie gibt an, dass es $A_j$ Raumpaare gibt, zwischen denen mindestens genau $j$ Wege durchlaufen werden müssen. Für jedes $j$ ($1 \le j \le R$) bewertet der Beispielgrader also einen Aufruf von Answer mit $j$ als Parameter D und $A_j$ als Parameter A als richtig und andere Antworten als falsch.

Der Beispielgrader ruft deine Routine auf, wobei sich der Spieler zu Beginn in Raum $1$ befindet.

Ausgabe des Beispielgraders

Wenn das Programm regulär endet, schreibt der Beispielgrader die folgenden Informationen in einer Zeile auf die Standardausgabe. Die Anführungszeichen werden nicht tatsächlich ausgegeben.

• Bei einer richtigen Antwort wird die Anzahl der Aufrufe von Move in einer Form wie Accepted : #move = 8 ausgegeben.
• Bei einer falschen Antwort wird deren Art in einer Form wie Wrong Answer [1] ausgegeben.

Beschränkungen

Alle Eingabedaten erfüllen die folgenden Bedingungen. Die Bedeutung von $N,D_i,T_{ij}$ ist im Abschnitt „Eingabe des Beispielgraders“ beschrieben.

• $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$ und $T_{ij}\ne i$ ($1 \le i \le N$, $1 \le j \le D_i$).
• $T_{i1},T_{i2},\ldots,T_{iD_i}$ sind paarweise verschieden ($1 \le i \le N$).
• Für alle $i,j$ ($1 \le i \le N$, $1 \le j \le D_i$) gibt es ein $k$ ($1 \le k \le D_{T_{ij}}$) mit $T_{T_{ij}k}=i$.
• Zwischen beliebigen zwei Räumen kann man über einige Wege gelangen.

Teilaufgaben

Im Folgenden bezeichnen $N$ die Anzahl der Räume und $M$ die Anzahl der Wege des Dungeons in den Eingabedaten.

Teilaufgabe 1 [17 Punkte]

Es gelten die folgenden Bedingungen.

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

Teilaufgabe 2 [27 Punkte]

Es gelten die folgenden Bedingungen.

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

Teilaufgabe 3 [56 Punkte]

• Es gilt $X=3$.

In dieser Teilaufgabe wird die Punktzahl wie folgt bestimmt.

• Sei $L$ das Maximum des folgenden Wertes über alle Testfälle dieser Teilaufgabe.

  • $\frac{C}{M}$, wobei $C$ die Anzahl der Aufrufe von Move ist.

• Die Punktzahl dieser Teilaufgabe beträgt dann:

  • 56 Punkte für $L \le 14$.
  • $\lfloor 70-L\rfloor$ Punkte für $14<L \le 32$.
  • $\left\lfloor 54-\frac{L}{2}\right\rfloor$ Punkte für $32<L \le 64$.
  • 0 Punkte für $64<L$.

Dabei bezeichnet $\lfloor x\rfloor$ die größte ganze Zahl, die $x$ nicht überschreitet.

Wenn das Programm regulär endet und als richtig bewertet wird, zeigt das Bewertungssystem im Detailfeld Accepted an. Beachte jedoch, dass bei der Bewertung von Teilaufgabe 3 für Testfälle, in denen die obigen Werte $C,M$ die Bedingung $64<\frac{C}{M}$ erfüllen, im Ergebnisfeld „Falsche Antwort“ angezeigt wird.

Interaktionsbeispiel

Im Folgenden werden eine Beispieleingabe für den Beispielgrader und die entsprechenden Routinenaufrufe gezeigt.

Eingabe 1

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

Beispielhafte Routinenaufrufe

Beachte, dass die Funktionsaufrufe in diesem Beispiel nicht unbedingt sinnvoll sein müssen.