Как-то раз Ли́са Симпсон, персонаж мультсериала «Симпсоны», оказалась в одной из вершин некоторого связного неориентированного графа. Лиса может передвигаться между соединенными ребром вершинами графа, однако, кроме вершины, в которой она на данный момент находится, а также всех смежных с ней вершин, девочке ничего не видно. К тому же у Лисы нет с собой ручки и бумаги, чтобы отмечать маршрут своих передвижений или другую информацию. Зато у нее есть неограниченное количество камешков, которые девочка может оставлять в вершинах графа, и именно этим она планирует воспользоваться, чтобы исследовать некоторые его свойства. К сожалению, в одной вершине графа помещается не больше чем 1000 камешков, но Лиса верит, что этого ей хватит. Известно, что количество вершин в графе не меньше 2 и не больше 500.
Задание
Данная задача состоит из двух подзадач:
В первой подзадаче ни в одной из вершин графа сначала нет камешков, а Лиса хочет выяснить, сколько вершин содержит граф.
Во второй подзадаче в одной из вершин графа (отличной от начальной) лежит один камешек, а в остальных вершинах — ни одного. Лиса хочет определить длину самого короткого пути по ребрам между начальной вершиной и той, где лежит камешек (длину каждого ребра считаем единичной).
Напишите процедуру 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);
Параметры процедуры
subproblem — номер подзадачи: 1 для подзадачи определения количества вершин, 2 для подзадачи поиска длины самого короткого пути. Номер подзадачи не меняется при запусках процедуры на одном и том же графе.
neighborsCount — количество смежных вершин, т. е. количество вершин, соединенных с текущей вершиной ребром.
neighbors — массив, содержащий ровно neighborsCount элементов (индексация с нуля) — количества камешков в смежных вершинах. Обратите внимание, что порядок смежных вершин может быть разным (произвольным образом переставленным) во время разных вызовов процедуры, даже если текущая вершина одна и та же. Содержимое этого массива процедура в случае необходимости может менять, но на реальном количестве камешков в соответствующих вершинах это никак не отражается: Лиса может менять количество камешков исключительно в той вершине, где она на данный момент находится.
current — количество камешков в текущей вершине. Это количество в процедуре можно изменить (как увеличить, так и уменьшить, но так, чтобы количество не стало отрицательным или большим чем 1000). При этом изменится и реальное количество камешков в соответствующей вершине графа.
whereToGo — начальное значение этого параметра (аргумент, который передает тело программы) равно -1. Если Лиса продолжает исследование графа, это значение нужно переписать, сделав равным количеству камешков в следующей вершине, куда должна пойти Лиса (обратите внимание: это не индекс в массиве neighbors, а значение!). Если в массиве neighbors есть сразу несколько элементов с такими значениями, Лиса пойдет в одну из соответствующих вершин, но то, в какую именно, процедура ограничить не может. Если Лиса на данном вызове процедуры уже готова дать ответ, начальное значение -1 этого параметра переписывать не нужно (и нельзя).
answer — начальное значение этого параметра (аргумент, который передает тело программы) также равно -1. Если Лиса готова дать ответ, это значение следует переписать, сделав его равным ответу. Если Лиса на данном вызове процедуры еще не готова дать ответ, начальное значение -1 этого параметра переписывать не нужно (и нельзя).
На каждом шаге процедура должна определять действия девочки, исходя исключительно из данных, переданных ей на этом шаге. На результат работы процедуры никоим образом не должно влиять предыдущее взаимодействие тела программы и процедуры. Кроме того, процедура должна быть детерминированной, т. е. для одинаковых входных данных всегда возвращать одни и те же значения.
Собственноручное тестирование
В электронном варианте условий приведен пример основного тела программы graph_tester.cpp/graph_tester.pas, которое запускает процедуру graph на графе, заданном в созданном вами входном файле, и выводит ответ, возвращенный процедурой, в выходной файл. Чтоб использовать эту программу, разместите ее в одном каталоге с файлом graph.cpp/graph.pas, который содержит вашу реализацию процедуры, и создайте в этом же каталоге файл graph.dat со структурой, описанной в следующем абзаце. Обратите внимание, что основное тело программы, которое будет использовано для оценивания вашей процедуры, будет отличаться от предоставленного вам в graph_tester.cpp/graph_tester.pas примера.
graph_tester: входные данные
Первая строка содержит четыре целых числа. Первые три — количество N вершин графа, количество M ребер графа и номер начальной вершины. При этом считаем, что вершины графа пронумерованы натуральными числами от 1 до N. Четвертое число равно 0, если вы тестируете процедуру на первой подзадаче, или равно номеру вершины, в которой лежит один камешек, если вы тестируете процедуру на второй подзадаче. Следующие M строк файла задают ребра графа: по два числа в строке в произвольном порядке — номера соединенных ребром вершин.
graph_tester: выходные данные
Единственная строка выходного файла будет содержать ответ, который после исследования графа вернула процедура, или словесную диагностику ошибки в случае, если на каком-либо шаге процедура нарушила технические требования.