Чи знаєте ви компанію Just Ordinary Inventions? Ця компанія займається «просто звичайними винаходами».

JOI грає в найновішу гру, розроблену компанією Just Ordinary Inventions.

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

Щоб допомогти гравцеві, у кожній кімнаті є орієнтир і п'єдестал. За орієнтиром можна пронумерувати проходи, що виходять із кімнати: перший, другий тощо. Структура підземелля під час гри не змінюється. Тому, виходячи з тієї самої кімнати через прохід з тим самим номером, гравець завжди потрапляє в ту саму кімнату. На п'єдесталі лежить один коштовний камінь, колір якого гравець може змінювати. Його колір є одним із кольорів $1,2,\ldots,X$; на початку гри камінь у кожній кімнаті має колір $1$. Колір каменя не змінюється, якщо гравець його не змінить.

JOI помітив, що якби він знав структуру підземелля, тобто те, як кімнати сполучені проходами, то міг би легко пройти гру. Однак, попри різні спроби, визначити структуру йому не вдалося. Тому ви вирішили написати програму, яка визначить структуру підземелля замість JOI.

Завдання

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

Для дослідження підземелля надається бібліотека, яка дозволяє виконувати такі дії:

• Дізнатися кількість проходів, що виходять із поточної кімнати.
• Дізнатися колір коштовного каменя на п'єдесталі в поточній кімнаті.
• Змінити колір коштовного каменя на п'єдесталі в поточній кімнаті на вказаний (можна вказати й поточний колір). Після цього вибрати один прохід із кімнати та перейти ним до іншої кімнати.
• Дізнатися номер останнього використаного проходу серед проходів, що виходять із поточної кімнати.

Деталі реалізації

Ви маєте написати одну програму, яка реалізує спосіб відповіді JOI. Програма має підключати dungeon2.h.

Програма має реалізувати таку процедуру:

• void Inspect(int R)

Ця процедура викликається лише один раз на початку.

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

Крім того, для надання відповіді потрібно викликати таку процедуру:

• void Answer(int D, int A)

• Аргументи D, A означають, що цим викликом ви повідомляєте: кількість пар кімнат, для яких найменша кількість проходів для переходу між ними дорівнює рівно $D$, становить $A$.

Виклики Answer мають задовольняти такі умови:

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

Якщо виклик Answer визнано неправильним, подальше виконання програми не гарантується.

Крім цього, у програмі можна викликати такі процедури:

• void Move(int I, int C)

• Аргумент I — номер проходу, який гравець вибирає для переходу. Одразу після цього виклику гравець переходить до іншої кімнати через $I$-й прохід із поточної кімнати.

• Аргумент C означає, що перед переходом колір каменя на п'єдесталі поточної кімнати змінюється на колір $C$.

Виклики Move мають задовольняти такі умови:

• Нехай із поточної кімнати виходить $K$ проходів. Аргумент I має бути цілим числом від $1$ до $K$ включно. Інакше результат — Wrong Answer [5].
• Якщо доступно $X$ кольорів каменя, аргумент C має бути цілим числом від $1$ до $X$ включно. Значення $X$ визначається для кожної підзадачі. Інакше результат — Wrong Answer [6].

• Не можна викликати Move більше ніж $1\,500\,000$ разів. Інакше результат — Wrong Answer [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$ до $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}$, розділених пробілами. Це означає, що перехід через $j$-й прохід ($1\le j\le D_i$) із кімнати $i$ приводить у кімнату $T_{ij}$.
• Рядок $j$ ($1\le j\le R$) із наступних $R$ рядків містить ціле число $A_j$. Це означає, що кількість пар кімнат, для яких найменша кількість проходів для переходу між ними дорівнює рівно $j$, становить $A_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$ — максимальне серед усіх тестів цієї підзадачі значення такої величини:

  • $\frac{C}{M}$, де $C$ — кількість викликів Move.

• Тоді кількість балів за цю підзадачу становить:

  • $56$ балів, якщо $L\le 14$.
  • $\lfloor70-L\rfloor$ балів, якщо $14<L\le 32$.
  • $\left\lfloor54-\frac{L}{2}\right\rfloor$ балів, якщо $32<L\le 64$.
  • $0$ балів, якщо $64<L$.

Тут $\lfloor x\rfloor$ означає найбільше ціле число, яке не перевищує $x$.

У системі оцінювання, якщо програма завершується коректно і відповідь визнано правильною, у полі деталей відображається Accepted. Однак зверніть увагу: під час оцінювання підзадачі 3 для тестів, у яких наведені вище $C,M$ задовольняють $64<\frac{C}{M}$, у полі результату відображається неправильна відповідь.

Приклад взаємодії

Нижче наведено приклад вхідних даних, які читає приклад програми оцінювання, та відповідні виклики процедур.

Вхідні дані 1

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

Приклад викликів процедур

Зверніть увагу, що виклики функцій у цьому прикладі не обов'язково є змістовними.