Знаете ли вы компанию Just Ordinary Inventions? Эта компания занимается «просто обычными изобретениями».

JOI-kun играет в новейшую игру, разработанную компанией Just Ordinary Inventions.

В этой игре нужно исследовать подземелье, состоящее из комнат и дорог. Каждая дорога соединяет две разные комнаты, и по ней можно перемещаться в обоих направлениях. Между любыми двумя различными комнатами существует не более одной дороги; дорог, оба конца которых находятся в одной комнате, нет. Также известно, что из любой комнаты подземелья можно добраться до любой другой, пройдя по нескольким дорогам. Все комнаты очень похожи: комнаты, из которых выходит одинаковое количество дорог, совершенно невозможно различить только по их виду.

Чтобы помочь игроку, в каждой комнате есть ориентир и постамент. Выходящие из комнаты дороги можно пронумеровать относительно ориентира: первая, вторая и так далее. Во время игры структура подземелья не меняется. Поэтому, выходя из одной и той же комнаты по дороге с одним и тем же номером, игрок всегда попадает в одну и ту же комнату. На постаменте находится один драгоценный камень, цвет которого игрок может менять. Камень может иметь один из цветов $1,2,\ldots,X$; в начале игры камни во всех комнатах имеют цвет $1$. Цвет камня не меняется, если игрок сам его не изменит.

JOI-kun понял, что игру будет легко пройти, если узнать структуру подземелья, то есть то, как комнаты соединены дорогами. Однако, несмотря на разные попытки, ему не удалось определить эту структуру. Поэтому вы решили написать вместо JOI-kun программу, определяющую структуру подземелья.

Задание

Напишите программу, которая исследует подземелье и определяет его структуру. Однако JOI-kun не хочет знать всю структуру подземелья, поэтому вместо непосредственного описания структуры программа должна для каждого целого $i$ от $1$ до $R$ сообщить количество пар комнат, для перемещения между которыми необходимо пройти как минимум ровно $i$ дорог. Пары, отличающиеся только порядком комнат, считаются одной парой.

Для исследования подземелья предоставляется библиотека, позволяющая выполнять следующие действия:

• Узнать количество дорог, выходящих из текущей комнаты.
• Узнать цвет камня на постаменте в текущей комнате.
• Изменить цвет камня на постаменте в текущей комнате на указанный цвет (можно указать и текущий цвет). Затем выбрать одну из дорог, выходящих из комнаты, и перейти по ней в другую комнату.
• Узнать, какой номер среди дорог, выходящих из текущей комнаты, имеет дорога, использованная последней.

Детали реализации

Нужно написать одну программу, реализующую способ сообщить ответ JOI-kun. Программа должна подключать dungeon2.h.

Программа должна реализовать следующую процедуру.

void Inspect(int R)

Эта процедура вызывается только один раз в самом начале.

• Параметр R означает, что для каждого целого $i$ от $1$ до $R$ нужно сообщить количество пар комнат, для перемещения между которыми необходимо пройти как минимум ровно $i$ дорог. Пары, отличающиеся только порядком комнат, считаются одной парой.

Также необходимо вызывать следующую процедуру, чтобы сообщать ответы.

void Answer(int D, int A)

• Параметры D и A означают, что этим вызовом вы сообщаете: «Существует $A$ пар комнат, для перемещения между которыми необходимо пройти как минимум ровно $D$ дорог».

Вызовы Answer должны удовлетворять следующим условиям.

• $D$ должно быть целым числом от $1$ до $R$ включительно. Иначе результат — неверный ответ [1].
• Нельзя вызывать Answer два или более раз с одним и тем же значением параметра D. Иначе результат — неверный ответ [2].
• Необходимо вызвать Answer ровно $R$ раз. Иначе результат — неверный ответ [3].
• $A$ должно равняться количеству пар комнат, для перемещения между которыми необходимо пройти как минимум ровно $D$ дорог. Иначе результат — неверный ответ [4].

Если вызов Answer признан неверным, дальнейшее выполнение программы не гарантируется.

Кроме того, программа может вызывать следующие процедуры и функции.

void Move(int I, int C)

• Параметр I — номер дороги, выбранной игроком для перемещения. Сразу после этого вызова игрок переходит в другую комнату по $I$-й дороге, выходящей из текущей комнаты.
• Параметр C означает, что перед переходом цвет камня на постаменте в текущей комнате меняется на цвет $C$.

Вызовы Move должны удовлетворять следующим условиям.

• Пусть $K$ — количество дорог, выходящих из текущей комнаты. Параметр I должен быть целым числом от $1$ до $K$ включительно. Иначе результат — неверный ответ [5].
• Пусть $X$ — количество доступных цветов камней. Параметр C должен быть целым числом от $1$ до $X$ включительно. Значение $X$ определяется подзадачей. Иначе результат — неверный ответ [6].
• Нельзя вызывать Move более $1\,500\,000$ раз. Иначе результат — неверный ответ [7].

int NumberOfRoads()

• Функция возвращает количество дорог, выходящих из комнаты, в которой сейчас находится игрок.

int LastRoad()

• Функция возвращает номер последней использованной игроком дороги среди дорог, выходящих из текущей комнаты. Если функция вызвана до первого вызова Move, она возвращает $-1$.

int Color()

• Функция возвращает цвет камня на постаменте в комнате, в которой сейчас находится игрок.

После вызова процедуры Inspect выполняется проверка ответов.

Можно реализовывать другие процедуры для внутреннего использования и объявлять глобальные переменные. Однако отправленное решение не должно никаким способом взаимодействовать со стандартным вводом, стандартным выводом или другими файлами.

Компиляция и запуск

Архив, доступный для скачивания на сайте соревнования, содержит пример проверяющей программы для тестирования вашего решения. В архиве также есть образец файла, который нужно отправить.

Пример проверяющей программы состоит из одного файла: grader.c или grader.cpp. Чтобы протестировать свою программу, выполните следующую команду.

Для C:

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

Для C++:

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

При успешной компиляции будет создан исполняемый файл grader.

Обратите внимание, что настоящая проверяющая программа отличается от примера. Пример запускается как один процесс, читает входные данные из стандартного ввода и выводит результат в стандартный вывод.

Входные данные примера проверяющей программы

Пример проверяющей программы читает следующие данные из стандартного ввода.

• В первой строке записаны целые числа $N,X,R$, разделённые пробелами. Они означают, что в подземелье $N$ комнат с номерами $1,2,\ldots,N$, камни могут иметь $X$ различных цветов, а программа должна сообщить $R$ значений.
• В строке $2i-1$ ($1 \le i \le N$) из следующих $2N$ строк записано целое число $D_i$, означающее, что из комнаты $i$ выходит $D_i$ дорог. В строке $2i$ ($1 \le i \le N$) записаны $D_i$ целых чисел $T_{i1},T_{i2},\ldots,T_{iD_i}$, разделённых пробелами. Это означает, что, выйдя из комнаты $i$ по дороге с номером $j$ ($1 \le j \le D_i$), игрок попадёт в комнату $T_{ij}$.
• В строке $j$ ($1 \le j \le R$) из следующих $R$ строк записано целое число $A_j$. Это означает, что существует $A_j$ пар комнат, для перемещения между которыми необходимо пройти как минимум ровно $j$ дорог. Иными словами, для каждого $j$ ($1 \le j \le R$) пример проверяющей программы признаёт правильным вызов Answer с параметром D, равным $j$, и параметром A, равным $A_j$; в остальных случаях ответ признаётся неправильным.

Пример проверяющей программы вызывает написанную вами процедуру, поместив игрока в начальную комнату $1$.

Выходные данные примера проверяющей программы

Если программа завершилась нормально, пример проверяющей программы выводит в стандартный вывод одну строку со следующей информацией (кавычки на самом деле не выводятся).

• При правильном ответе выводится количество вызовов Move, например Accepted : #move = 8.
• При неправильном ответе выводится тип ошибки, например Wrong Answer [1].

Ограничения

Все входные данные удовлетворяют следующим условиям. Значения $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$ и $T_{ij} \ne i$ ($1 \le i \le N$, $1 \le j \le D_i$).
• Значения $T_{i1},T_{i2},\ldots,T_{iD_i}$ попарно различны ($1 \le i \le N$).
• Для каждых $i,j$ ($1 \le i \le N$, $1 \le j \le D_i$) существует $k$ ($1 \le k \le D_{T_{ij}}$), для которого $T_{T_{ij},k}=i$.
• Между любыми двумя комнатами можно перемещаться по нескольким дорогам.

Подзадачи

Далее $N$ обозначает количество комнат в подземелье во входных данных, а $M$ — количество дорог.

Подзадача 1 [17 баллов]

Выполняются следующие условия.

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

Подзадача 2 [27 баллов]

Выполняются следующие условия.

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

Подзадача 3 [56 баллов]

• Выполняется $X=3$.

В этой подзадаче баллы определяются следующим образом.

• Пусть $L$ — наибольшее среди всех тестов этой подзадачи значение следующей величины.
• Если $C$ — количество вызовов Move, эта величина равна $\dfrac{C}{M}$.

Тогда количество баллов за эту подзадачу равно:

• 56, если $L \le 14$.
• $\lfloor 70-L \rfloor$, если $14 < L \le 32$.
• $\left\lfloor 54-\dfrac{L}{2}\right\rfloor$, если $32 < L \le 64$.
• 0, если $64 < L$.

Здесь $\lfloor x \rfloor$ обозначает наибольшее целое число, не превосходящее $x$.

Если программа завершилась нормально и ответ признан правильным, система проверки показывает Accepted в поле подробностей. Однако обратите внимание: при проверке подзадачи 3 для теста, в котором указанные выше $C$ и $M$ удовлетворяют $64 < \dfrac{C}{M}$, в поле результата показывается неверный ответ.

Примеры

Ниже приведены пример входных данных для примера проверяющей программы и соответствующая последовательность вызовов процедур и функций.

Входные данные 1

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

Пример вызовов

Обратите внимание, что вызовы функций в этом примере не обязательно имеют осмысленное назначение.