Czy znasz firmę Just Ordinary Inventions? Jej działalność polega na tworzeniu „zwyczajnych wynalazków”.

JOI gra w najnowszą grę opracowaną przez firmę Just Ordinary Inventions.

Gra polega na zwiedzaniu lochu złożonego z pewnej liczby komnat i dróg. Każda droga łączy dwie różne komnaty i można nią podróżować w obu kierunkach. Dowolne dwie różne komnaty łączy co najwyżej jedna droga; nie ma dróg, których oba końce znajdują się w tej samej komnacie. Wiadomo też, że między dowolnymi dwiema komnatami można przejść, korzystając z pewnej liczby dróg. Komnaty wyglądają bardzo podobnie: komnat, z których wychodzi tyle samo dróg, nie da się w ogóle rozróżnić na podstawie ich wyglądu.

Aby ułatwić grę, w każdej komnacie znajdują się znak orientacyjny i postument. Drogi wychodzące z komnaty można numerować względem znaku jako pierwszą, drugą i tak dalej. Struktura lochu nie zmienia się podczas gry. Dlatego wyjście z tej samej komnaty drogą o tym samym numerze zawsze prowadzi do tej samej komnaty. Na postumencie znajduje się jeden klejnot, którego kolor gracz może zmieniać. Klejnot może mieć kolor $1,2,\ldots,X$; na początku gry wszystkie klejnoty mają kolor $1$. Kolor klejnotu nie zmienia się, dopóki gracz go nie zmieni.

JOI zauważył, że gdyby znał strukturę lochu, czyli sposób połączenia komnat drogami, łatwo mógłby ukończyć grę. Mimo wielu prób nie zdołał jednak ustalić tej struktury. Postanawiasz więc napisać program, który ustali ją za niego.

Zadanie

Napisz program, który zbada loch i ustali jego strukturę. JOI nie chce jednak poznać jej w całości, dlatego zamiast podawać strukturę bezpośrednio, program ma dla każdej liczby całkowitej $i$ od $1$ do $R$ odpowiedzieć na pytanie: „Ile jest par komnat, między którymi najkrótsza droga wykorzystuje dokładnie $i$ dróg?”. Zamiana kolejności komnat nie tworzy nowej pary.

Do badania lochu otrzymujesz bibliotekę umożliwiającą następujące działania:

• Poznanie liczby dróg wychodzących z bieżącej komnaty.
• Poznanie koloru klejnotu na postumencie w bieżącej komnacie.
• Ustawienie koloru klejnotu w bieżącej komnacie na wskazany kolor (można wskazać także jego obecny kolor), a następnie wybranie jednej z wychodzących dróg i przejście nią do innej komnaty.
• Poznanie numeru ostatnio użytej drogi wśród dróg wychodzących z bieżącej komnaty.

Szczegóły implementacji

Musisz napisać jeden program implementujący sposób udzielania odpowiedzi JOI. Program musi dołączać plik dungeon2.h.

Program musi implementować następującą procedurę.

• void Inspect(int R)

  Procedura jest wywoływana dokładnie raz na początku.

  • Parametr R oznacza, że dla każdej liczby całkowitej $i$ od $1$ do $R$ musisz podać liczbę par komnat, między którymi najkrótsza droga wykorzystuje dokładnie $i$ dróg. Zamiana kolejności komnat nie tworzy nowej pary.

Musisz także wywoływać poniższą procedurę, aby udzielać odpowiedzi.

• void Answer(int D, int A)

  • Parametry D i A oznaczają, że to wywołanie podaje odpowiedź: „Istnieje $A$ par komnat, między którymi najkrótsza droga wykorzystuje dokładnie $D$ dróg”.

  Wywołania Answer muszą spełniać następujące warunki.

  • D musi być liczbą całkowitą od $1$ do $R$. W przeciwnym razie otrzymasz werdykt błędnej odpowiedzi [1].
  • Nie wolno wywołać Answer co najmniej dwa razy z tym samym argumentem D. W przeciwnym razie otrzymasz werdykt błędnej odpowiedzi [2].
  • Answer należy wywołać dokładnie $R$ razy. W przeciwnym razie otrzymasz werdykt błędnej odpowiedzi [3].
  • A musi być liczbą par komnat, między którymi najkrótsza droga wykorzystuje dokładnie $D$ dróg. W przeciwnym razie otrzymasz werdykt błędnej odpowiedzi [4].

  Jeśli wywołanie Answer zostanie uznane za błędne, dalsze wykonywanie programu nie jest gwarantowane.

Ponadto program może wywoływać następujące procedury.

• void Move(int I, int C)

  • Parametr I jest numerem drogi wybranej przez gracza. Bezpośrednio po tym wywołaniu gracz przechodzi do innej komnaty drogą numer $I$ wychodzącą z bieżącej komnaty.
  • Parametr C oznacza, że przed przejściem do innej komnaty kolor klejnotu na postumencie w bieżącej komnacie zostaje ustawiony na kolor $C$.

  Wywołania Move muszą spełniać następujące warunki.

  • Jeśli z bieżącej komnaty gracza wychodzi $K$ dróg, argument I musi być liczbą całkowitą od $1$ do $K$. W przeciwnym razie otrzymasz werdykt błędnej odpowiedzi [5].
  • Jeśli dostępnych jest $X$ kolorów klejnotów, argument C musi być liczbą całkowitą od $1$ do $X$. Wartość $X$ zależy od podzadania. W przeciwnym razie otrzymasz werdykt błędnej odpowiedzi [6].
  • Nie wolno wywołać Move więcej niż $1\,500\,000$ razy. W przeciwnym razie otrzymasz werdykt błędnej odpowiedzi [7].

• int NumberOfRoads()

  • Funkcja zwraca liczbę dróg wychodzących z komnaty, w której znajduje się gracz.

• int LastRoad()

  • Funkcja zwraca numer ostatnio użytej przez gracza drogi wśród dróg wychodzących z bieżącej komnaty. Jeśli jednak zostanie wywołana przed pierwszym wywołaniem Move, zwraca $-1$.

• int Color()

  • Funkcja zwraca kolor klejnotu na postumencie w komnacie, w której znajduje się gracz.

Po wywołaniu procedury Inspect odpowiedzi zostaną sprawdzone.

Możesz implementować inne procedury na użytek wewnętrzny i deklarować zmienne globalne. Twoje rozwiązanie nie może jednak w żaden sposób korzystać ze standardowego wejścia, standardowego wyjścia ani komunikować się z innymi plikami.

Kompilacja i uruchamianie

Archiwum dostępne do pobrania na stronie konkursu zawiera przykładowy program oceniający, którym można przetestować rozwiązanie. Zawiera także przykładowe pliki, które należy przesłać.

Przykładowy program oceniający składa się z jednego pliku: grader.c lub grader.cpp. Aby przetestować napisany program, wykonaj odpowiednie polecenie.

• Dla C:

  gcc -std=c11 -O2 -o grader grader.c dungeon2.c -lm

• Dla C++:

  g++ -std=c++11 -O2 -o grader grader.cpp dungeon2.cpp

Jeśli kompilacja się powiedzie, powstanie plik wykonywalny grader.

Pamiętaj, że właściwy program oceniający różni się od przykładowego. Przykładowy program jest uruchamiany jako jeden proces. Czyta dane ze standardowego wejścia i wypisuje wyniki na standardowe wyjście.

Wejście przykładowego programu oceniającego

Przykładowy program oceniający czyta następujące dane ze standardowego wejścia.

• Pierwszy wiersz zawiera liczby całkowite $N,X,R$, oddzielone spacjami. Oznaczają one, że loch ma $N$ komnat o numerach $1,2,\ldots,N$, klejnoty mają $X$ możliwych kolorów, a program musi podać $R$ wartości.
• Wśród kolejnych $2N$ wierszy wiersz $2i-1$ ($1 \le i \le N$) zawiera liczbę całkowitą $D_i$, oznaczającą liczbę dróg wychodzących z komnaty $i$. Wiersz $2i$ ($1 \le i \le N$) zawiera $D_i$ liczb całkowitych $T_{i1},T_{i2},\ldots,T_{iD_i}$, oddzielonych spacjami. Oznacza to, że droga numer $j$ ($1 \le j \le D_i$) wychodząca z komnaty $i$ prowadzi do komnaty $T_{ij}$.
• Wiersz $j$ ($1 \le j \le R$) spośród kolejnych $R$ wierszy zawiera liczbę całkowitą $A_j$. Oznacza to, że istnieje $A_j$ par komnat, między którymi najkrótsza droga wykorzystuje dokładnie $j$ dróg. Innymi słowy, dla każdego $j$ ($1 \le j \le R$) przykładowy program oceniający uzna odpowiedź za poprawną, jeśli wywołasz Answer z argumentem D równym $j$ i argumentem A równym $A_j$; w przeciwnym razie uzna ją za błędną.

Przykładowy program oceniający ustawia początkową pozycję gracza na komnatę $1$ i wywołuje napisaną przez ciebie procedurę.

Wyjście przykładowego programu oceniającego

Jeśli program zakończy się normalnie, przykładowy program oceniający wypisze w jednym wierszu standardowego wyjścia poniższą informację (cudzysłowy nie są wypisywane).

• Jeśli odpowiedź jest poprawna, liczba wywołań Move jest wypisywana na przykład jako Accepted : #move = 8.
• Jeśli odpowiedź jest błędna, jej rodzaj jest wypisywany na przykład jako Wrong Answer [1].

Ograniczenia

Wszystkie dane wejściowe spełniają poniższe warunki. Znaczenie $N,D_i,T_{ij}$ opisano w sekcji „Wejście przykładowego programu oceniającego”.

• $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$ oraz $T_{ij} \ne i$ ($1 \le i \le N$, $1 \le j \le D_i$).
• $T_{i1},T_{i2},\ldots,T_{iD_i}$ są parami różne ($1 \le i \le N$).
• Dla każdych $i,j$ ($1 \le i \le N$, $1 \le j \le D_i$) istnieje $k$ ($1 \le k \le D_{T_{ij}}$), takie że $T_{T_{ij}k}=i$.
• Między dowolnymi dwiema komnatami można przejść, korzystając z pewnej liczby dróg.

Podzadania

W dalszej części przez $N$ oznaczamy liczbę komnat, a przez $M$ liczbę dróg w lochu opisanym w danych wejściowych.

Podzadanie 1 [17 punktów]

Spełnione są następujące warunki.

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

Podzadanie 2 [27 punktów]

Spełnione są następujące warunki.

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

Podzadanie 3 [56 punktów]

• Spełniony jest warunek $X=3$.

W tym podzadaniu punkty przyznawane są według następujących zasad.

• Niech $L$ będzie największą wartością poniższego wyrażenia we wszystkich testach tego podzadania.

  • $\frac{C}{M}$, gdzie $C$ jest liczbą wywołań Move.

• Wtedy liczba punktów za to podzadanie wynosi:

  • $56$, jeśli $L \le 14$.
  • $\lfloor 70-L \rfloor$, jeśli $14 < L \le 32$.
  • $\left\lfloor 54-\frac{L}{2} \right\rfloor$, jeśli $32 < L \le 64$.
  • $0$, jeśli $64 < L$.

Tutaj $\lfloor x \rfloor$ oznacza największą liczbę całkowitą nieprzekraczającą $x$.

W systemie oceniającym, jeśli program zakończy się prawidłowo i odpowiedź zostanie uznana za poprawną, w kolumnie szczegółów pojawi się Accepted. Pamiętaj jednak, że w podzadaniu 3 dla testów, w których powyższe $C,M$ spełniają $64 < \frac{C}{M}$, w kolumnie wyniku pojawi się informacja o błędnej odpowiedzi.

Przykład interakcji

Poniżej podano przykładowe dane wejściowe czytane przez przykładowy program oceniający i odpowiadające im wywołania procedur.

Wejście 1

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

Przykładowe wywołania procedur

Zwróć uwagę, że wywołania funkcji w tym przykładzie nie muszą być sensowne.