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's 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 is divided into two parts:

1. Subproblem 1: Starting with no pebbles on any vertex, Lisa needs to determine the total number of vertices in the graph.

2. Subproblem 2: With one pebble placed on a vertex different from the starting one, Lisa must find the shortest path length from the starting vertex to the vertex with the pebble, assuming each edge has a unit length.

You need to implement a procedure graph that, based on the number of pebbles in the current vertex and its neighbors, decides Lisa's next move: how many pebbles to leave or take from the current vertex, and which adjacent vertex to move to next. Alternatively, when Lisa is ready to answer the subproblem, the procedure should provide the answer.

Implementation Details

Submit a file with the graph procedure implementation, without a main program body. During testing, your file will be combined with a special program body that will call your procedure and verify its correctness. The procedure should have the following signature:

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

Parameters

1. subproblem: Indicates the subproblem (1 or 2). This value remains constant for a given graph.

2. neighborsCount: The number of vertices adjacent to the current vertex.

3. neighbors: An array of size neighborsCount indicating the number of pebbles in each adjacent vertex. The order of vertices may change between calls.

4. current: The number of pebbles in the current vertex, which can be modified within the procedure (ensuring it remains between 0 and 1000).

5. whereToGo: Initially set to -1. If Lisa continues exploring, set this to the number of pebbles in the vertex to move to next. If ready to answer, leave it unchanged.

6. answer: Initially set to -1. If ready to answer, set this to the solution. Otherwise, leave it unchanged.

The procedure should determine Lisa's actions based solely on the current step's data, without relying on previous interactions. It must be deterministic, producing the same output for identical inputs.

Self-Testing

An example main program graph_tester.cpp/graph_tester.pas is provided to test your procedure. It reads a graph from an input file, runs the graph procedure, and writes the result to an output file. Place this tester in the same directory as your graph.cpp/graph.pas file and create a graph.dat file with the following structure:

• The first line contains four integers: the number of vertices N, the number of edges M, the starting vertex number, and either 0 (for subproblem 1) or the vertex number with a pebble (for subproblem 2).

• The next M lines list the edges, each defined by two vertex numbers.

The output file will contain the procedure's answer or an error message if any technical requirements are violated.

Evaluation

The test set consists of four blocks with additional conditions:

1. 30 points: Subproblem 1, the graph is a tree.

2. 20 points: Subproblem 1, the graph is not necessarily a tree.

3. 10 points: Subproblem 2, the graph is a tree.

4. 40 points: Subproblem 2, the graph is not necessarily a tree.

Note: If your procedure violates the requirements during testing, you may receive a runtime or compilation error. The memory limit is at least 16 MB. Global variables are allowed.

Examples