Graph from the Inside

Lisa Simpson, a character from the animated series "The Simpsons," finds herself at a vertex of a connected undirected graph. She can move between vertices connected by an edge, but she can only see the vertex she is currently in and its directly connected neighbors. Without pen and paper, Lisa uses pebbles to explore the graph. She can place up to $1000$ pebbles on a vertex, which she believes is sufficient. The graph has between $2$ and $500$ vertices.

Objective

The problem consists of two subproblems:

1. In the first subproblem, there are initially no pebbles on any vertex, and Lisa wants to determine the total number of vertices in the graph.

2. In the second subproblem, there is one pebble placed on some vertex (different from the starting one), and none in the others. Lisa wants to find the shortest path length (by edges) between the starting vertex and the vertex with the pebble, assuming each edge has unit length.

You need to write a procedure graph that, based on the number of pebbles in the current vertex and all its neighbors, decides the next step for Lisa: how many pebbles to leave or take from the current vertex, and which adjacent vertex to move to next; or, when Lisa is ready to answer the problem, returns this answer.

Implementation Details

You must submit a file containing the implementation of the procedure graph, as described below, and (if necessary) additional code required for the correct execution of this procedure, but without the main function body (e.g., main in C++ or begin/end block in Pascal). During testing, your file will be combined with a special program body written by the jury. This main body will appropriately call your procedure and check the correctness of the implemented algorithm. Your implementation must conform to the following signatures:

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);

Procedure Parameters

1. subproblem — subproblem number: $1$ for counting vertices, $2$ for finding the shortest path. The subproblem number does not change for calls on the same graph.

2. neighborsCount — the number of adjacent vertices, i.e., vertices connected by an edge to the current vertex.

3. neighbors — an array with exactly neighborsCount elements ($0$-indexed): the numbers of pebbles in the neighboring vertices. The order of neighbors may vary arbitrarily between different calls to the procedure, even if the current vertex is the same. The content of this array may be modified within the procedure if necessary, but this does not affect the actual number of pebbles in the corresponding vertices: Lisa can change the number of pebbles only in the vertex she is currently in.

4. current — the number of pebbles in the current vertex. This number may be modified within the procedure (increased or decreased, but must not become negative or exceed $1000$). This also changes the actual number of pebbles in the corresponding vertex of the graph.

5. whereToGo — its initial value (the argument as received from the main program) is $-1$. If Lisa continues exploring the graph, you must update this value, setting it to the number of pebbles in the next vertex Lisa will move to (note: this is a value, not an index in the neighbors array!). If there are several elements in neighbors with the same value, Lisa will move to one of the corresponding vertices, but the procedure cannot control which one. If Lisa is ready to answer, you should leave the initial value $-1$ unchanged (and must not modify it).

6. answer — its initial value (the argument as received from the main program) is also $-1$. If Lisa is ready to answer, set this value to the answer. If Lisa is not ready, you should leave the initial value $-1$ unchanged (and must not modify it).

At each step, the procedure should determine Lisa's actions based solely on the data passed at this step. Previous interaction between the procedure and main program must not affect the result. The procedure must also be deterministic: for the same input data, it must always return the same result.

Self-Testing

An example main program (graph_tester.cpp / graph_tester.pas) is provided to run your procedure on a graph specified in your input file, and outputs the answer returned by your procedure to the output file. To use this test program, place it in the same directory as your graph.cpp / graph.pas file which contains your procedure, and create a graph.dat file in the same directory with the structure described below. Note that the main program body used for evaluation will differ from the example provided to you.