The Xedef Courier Company provides air package delivery among several cities. Some of these cities are Xedef *hubs*where special processing facilities are established. Each of Xedef’s aircraft shuttles back and forth between one pair of cities, carrying packages in either direction as required.

To be shipped from one city to another, a package must be transported by a sequence of hops, where each hop carries the package between a pair of cities served by one of the aircraft. Furthermore, the sequence must include at least one of Xedef’s hubs.

To facilitate routing, Xedef wishes to encode the length of the shortest sequence of hops from every city to every hub on the shipping label of every package. (The length of the shortest sequence leading from a hub to itself is zero.) Obviously, a compact representation of this information is required.

You are to implement two procedures, **encode(N,H,P,A,B)** and **decode(N,H)**. **N** is the number of cities and **H** is the number of hubs. Assume that the cities are numbered from 0 to N-1, and that the hubs are the cities with numbers between 0 and H-1. Further assume that N ≤ 1000 and H ≤ 36. **P** is the number of pairs of cities connected by aircraft. All (unordered) pairs of cities will be distinct. **A** and **B** are arrays of size P, such that the first pair of connected cities is (A[0],B[0]), the second pair is (A[1],B[1]), and so on.

**encode** must compute a sequence of bits from which **decode** can determine the number of hops from every city to every hub. **encode** will transmit the sequence of bits to the grading server by a sequence of calls to **encode_bit(b)** where **b** is either 0 or 1. **decode** will receive the sequence of bits from the grading server by making calls to **decode_bit**. The *i*-th call to **decode_bit** will return the value of **b** from the *i*-th call to **encode_bit(b)**. Note that you must ensure that the number of times **decode** calls **decode_bit** will always be at most equal to the number of times **encode** previously called **encode_bit(b)**.

After decoding the numbers of hops, **decode** must call **hops(h,c,d)** for every hub **h** and every city **c** (including every hub, that is, also for **c**=**h**), giving the minimum number **d** of hops necessary to ship a package between **h** and **c**. That is, there must be N*H calls to **hops(h,c,d)**. The order does not matter. You are guaranteed that it is always possible to ship a package between every hub and every city.

*Note: encode and decode must communicate only through the specified interface. Shared variables, file access and network access are prohibited. In C or C++, you may declare persistent variables to be static to retain information for encode or decode, while preventing them from being shared. In Pascal, you may declare persistent variables in the implementation part of your solution files.*

## Example

As an example, consider the diagram on the right. It shows five cities (N=5) connected by seven aircraft (P=7). Cities 0, 1 and 2 are hubs (H=3). One hop is needed to ship a package between hub 0 and city 3, whereas 2 hops are needed to ship a package between hub 2 and city 3. The data for this example are in `grader.in.1`.

The entries in the following table are all **d**-values that **decode** must deliver by calling **hops(h,c,d)**:

d City c 0 1 2 3 4 Hub h 0 0 1 1 1 1 1 1 0 1 1 1 2 1 1 0 2 2

## Subtask 1 [25 points]

**encode** must make no more than 16 000 000 calls to **encode_bit(b)**.

## Subtask 2 [25 points]

**encode** must make no more than 360 000 calls to **encode_bit(b)**.

## Subtask 3 [25 points]

**encode** must make no more than 80 000 calls to **encode_bit(b)**.

## Subtask 4 [25 points]

**encode** must make no more than 70 000 calls to **encode_bit(b)**.

## Implementation Details

- Use the RunC programming and test environment
- Implementation folder:
`/home/ioi2010-contestant/saveit/`(prototype: saveit.zip) - To be implemented by contestant:
`encoder.c`or`encoder.cpp`or`encoder.pas``decoder.c`or`decoder.cpp`or`decoder.pas`

- Contestant interface:
`encoder.h`or`encoder.pas``decoder.h`or`decoder.pas`

- Grader interface:
`grader.h`or`graderlib.pas` - Sample grader:
`grader.c`or`grader.cpp`or`grader.pas`*and*`graderlib.pas` - Sample grader input:
`grader.in.1``grader.in.2`etc.

*Note: The first line of each file contains*`N``P``H`. The next`P`lines contain the pairs of cities`A[0] B[0]`,`A[1] B[1]`, etc. The next`H*N`lines contain the numbers of hops from each hub to each city (including itself and all other hubs); that is, the number of hops from a hub`i`to a city`j`is in the`i`*`N`+`j`+1 -st of these lines. - Expected output for sample grader input:
- If the implementation is correct for subtask 1, the output will contain
`OK 1` - If the implementation is correct for subtask 2, the output will contain
`OK 2` - If the implementation is correct for subtask 3, the output will contain
`OK 3` - If the implementation is correct for subtask 4, the output will contain
`OK 4`

- If the implementation is correct for subtask 1, the output will contain
- Compile and run (command line):
`runc grader.c`or`runc grader.cpp`or`runc grader.pas` - Compile and run (gedit plugin):
*Control-R*, while editing any implementation file. - Submit (command line):
`submit grader.c`or`submit grader.cpp`or`submit grader.pas` - Submit (gedit plugin):
*Control-J*, while editing any implementation or grader file.

Spoiler for: Solution | Show |
---|---|