Граф з середини

Ліса Сімпсон, персонаж мультсеріалу «Сімпсони», опинилася в одній із вершин зв'язного неорієнтованого графа. Вона може переходити між вершинами, з'єднаними ребром, але бачить лише ту вершину, в якій знаходиться, і її безпосередніх сусідів. Оскільки в неї немає ручки й паперу, Ліса використовує камінці для дослідження графа. В одній вершині можна розмістити до $1000$ камінців, цього, на її думку, достатньо. У графі від $2$ до $500$ вершин.

Завдання

Задача складається з двох підзадач:

1. У першій підзадачі в жодній вершині графа спочатку немає камінців, і Ліса має визначити кількість вершин у графі.

2. У другій підзадачі в одній з вершин (відмінній від початкової) розміщено один камінець, в інших — немає. Ліса має визначити довжину найкоротшого шляху (за кількістю ребер) від початкової вершини до тієї, де лежить камінець, припускаючи, що довжина кожного ребра дорівнює одиниці.

Необхідно написати процедуру graph, яка, отримуючи інформацію про кількість камінців у поточній вершині та в сусідніх вершинах, визначає наступний крок для Ліси: скільки камінців залишити чи забрати з поточної вершини і в яку із суміжних вершин перейти; або, коли Ліса готова дати відповідь — повертає її.

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

Ви маєте подати файл із реалізацією процедури graph, описаної нижче, і, за потреби, додатковий код, необхідний для коректної роботи цієї процедури, але без основного тіла програми (наприклад, без main у C++ чи блоку begin/end у Pascal). Під час тестування ваш файл буде об'єднано зі спеціально підготованим основним тілом програми. Вашу процедуру буде викликано та перевірено коректність алгоритму. Процедура повинна бути оголошена так:

C++:

void graph(int subproblem, int neighborsCount, int neighbors[], int &current, int &whereToGo, int &answer);

Pascal:

procedure graph(subproblem, neighborsCount: longint; var neighbors: array of longint; var current, whereToGo, answer: longint);

Параметри процедури

1. subproblem — номер підзадачі: $1$ для підрахунку вершин, $2$ для пошуку найкоротшого шляху. Номер підзадачі є сталим для одного графа.

2. neighborsCount — кількість суміжних вершин, тобто тих, що з'єднані ребром із поточною.

3. neighbors — масив із neighborsCount елементів (нумерація з нуля): кількості камінців у суміжних вершинах. Порядок елементів може змінюватись між викликами навіть для однієї й тієї самої вершини. Можна змінювати вміст цього масиву всередині процедури, але це не впливає на реальні дані — Ліса може змінювати кількість камінців лише у поточній вершині.

4. current — кількість камінців у поточній вершині. Можна змінювати (збільшувати чи зменшувати), але не залишати від'ємної чи більшої за $1000$. Це також змінює реальну кількість камінців у відповідній вершині графа.

5. whereToGo — початкове значення (аргумент від основної програми) дорівнює $-1$. Якщо Ліса продовжує дослідження, це значення треба змінити на кількість камінців у вершині, куди Ліса повинна піти далі (це не індекс у масиві neighbors, а значення!). Якщо таких значень кілька, Ліса піде в одну з них, але яку саме — процедура не контролює. Якщо Ліса готова дати відповідь — значення залишаєте $-1$.

6. answer — початкове значення (аргумент від основної програми) теж $-1$. Якщо Ліса готова дати відповідь — змініть це значення на відповідь, інакше залиште $-1$.

На кожному кроці дії визначаються лише даними поточного кроку. Попередні стани або взаємодія з основною програмою не повинні впливати на поведінку процедури. Вона повинна бути детермінованою: для однакових вхідних даних результат завжди той самий.

Самостійне тестування

Зразок основної програми (graph_tester.cpp/graph_tester.pas) запускає вашу процедуру для графа із вхідного файлу та виводить отриману відповідь у вихідний. Щоб нею скористатися, розмістіть всі потрібні файли разом та створіть файл graph.dat описаного нижче формату. Фінальне основне тіло програми може відрізнятися від прикладу.