Humanity's Last Code Exam / 2012_G / Minimum Cost Flow

## Problem Statement

You have been hired to construct a system to transport water between two points in an old factory building using some existing components of the old plumbing. The old components consist of pipes and junctions. Junctions are points where pipes may have previously been joined. We say previously joined, because some of the old pipes were damaged and have been removed, effectively leaving open holes in the junctions to which they were connected. If water should enter one of these junctions, it would pour out of an open hole and eventually flood the building—clearly an undesirable event.

You can remedy this situation by installing new pipes between some of the open holes and installing plugs to close other open holes as necessary. When you install a new pipe connecting two holes (which must be in two different junctions), the two holes are no longer open and water will be able to flow through the new pipe. The cost of installing a new pipe is equal to the distance between the centers of the two junctions the pipe connects. The cost of installing a plug in an open hole is 0.5. You are not concerned about open holes in junctions that will never be reached by water.

Two of the junctions are special. One, called the source, is the point where water will be pumped into the new system. The other, called the destination, is where the water is needed. After any plugs and new pipes have been added to the system, water will be pumped into it at the source with a pressure sufficient to reach a specified height (in the absence of leaks, of course). You are allowed to select the pressure arbitrarily, and are guaranteed that the pressure will not change during the operation of the system. Naturally the pressure must be sufficient to force water up to the heights of both the source and the destination. Your task is simply to find the most inexpensive way of getting water from the source junction to the destination junction without flooding the building.

Water flows through the system according to the laws of physics. If the pressure is sufficient to fill a junction with water, then that junction will remain filled with water. If there are pipes extending horizontally or downward from a junction, then water will also flow through those pipes. Water will also flow upward through pipes connected to a junction up to the height determined by the water pressure. Of course, if the water reaches an open hole in a junction, it will flow through the hole and flood the building.

Assume existing pipes and any new pipes do not interfere with each other or with any junctions, except those to which they are connected. That is, even if a straight line from junction A to junction B passes through junction C, any pipe from A to B will not touch C.

## Input

The first line of each test case contains two integers N and M, where N (2 ≤ N ≤ 400) is the number of junctions in the building (numbered 1 through N) and M (0 ≤ M ≤ 50,000) is the number of existing usable pipes.

Each of the next N lines contains four integers x_(i), y_(i), z_(i), and k_(i) satisfying \(-10,000 ≤ x_i, y_i, z_i ≤ 10,000\) and \(0 ≤ k_i ≤ 400\), i=1,2,…,N. The i-th line describes junction i: (x_(i),y_(i),z_(i)) is the location of the i-th junction where the z-axis is the vertical axis; k_(i) indicates the number of open holes in the junction.

Each of the next M lines contains two integers a_(j) and b_(j) satisfying \(1 ≤ a_j < b_j ≤ N\). The j-th line indicates that pipe j connects junctions a_(j) and b_(j). At most one pipe connects any pair of junctions, and no two junctions share the same coordinates. The source is junction 1, and the destination is junction N.

## Output

For each case, display the case number. Then if suitable new pipes and plugs can be used to construct the desired system, display the minimum cost of connecting the source junction to the destination junction, accurate to four decimal places. If it is impossible to connect the source to the destination, display the word `impossible`.

## Sample Input

## Problem Statement

You have been hired to construct a system to transport water between two points in an old factory building using some existing components of the old plumbing. The old components consist of pipes and junctions. Junctions are points where pipes may have previously been joined. We say previously joined, because some of the old pipes were damaged and have been removed, effectively leaving open holes in the junctions to which they were connected. If water should enter one of these junctions, it would pour out of an open hole and eventually flood the building—clearly an undesirable event.

You can remedy this situation by installing new pipes between some of the open holes and installing plugs to close other open holes as necessary. When you install a new pipe connecting two holes (which must be in two different junctions), the two holes are no longer open and water will be able to flow through the new pipe. The cost of installing a new pipe is equal to the distance between the centers of the two junctions the pipe connects. The cost of installing a plug in an open hole is 0.5. You are not concerned about open holes in junctions that will never be reached by water.

Two of the junctions are special. One, called the source, is the point where water will be pumped into the new system. The other, called the destination, is where the water is needed. After any plugs and new pipes have been added to the system, water will be pumped into it at the source with a pressure sufficient to reach a specified height (in the absence of leaks, of course). You are allowed to select the pressure arbitrarily, and are guaranteed that the pressure will not change during the operation of the system. Naturally the pressure must be sufficient to force water up to the heights of both the source and the destination. Your task is simply to find the most inexpensive way of getting water from the source junction to the destination junction without flooding the building.

Water flows through the system according to the laws of physics. If the pressure is sufficient to fill a junction with water, then that junction will remain filled with water. If there are pipes extending horizontally or downward from a junction, then water will also flow through those pipes. Water will also flow upward through pipes connected to a junction up to the height determined by the water pressure. Of course, if the water reaches an open hole in a junction, it will flow through the hole and flood the building.

Assume existing pipes and any new pipes do not interfere with each other or with any junctions, except those to which they are connected. That is, even if a straight line from junction A to junction B passes through junction C, any pipe from A to B will not touch C.

## Input

The first line of each test case contains two integers \( N \) and \( M \), where \( N \) (2 ≤ \( N \) ≤ 400) is the number of junctions in the building (numbered 1 through \( N \)) and \( M \) (0 ≤ \( M \) ≤ 50,000) is the number of existing usable pipes.

Each of the next \( N \) lines contains four integers \( x_i \), \( y_i \), \( z_i \), and \( k_i \) satisfying \(-10,000 ≤ x_i, y_i, z_i ≤ 10,000\) and \(0 ≤ k_i ≤ 400\), \( i = 1, 2, \ldots, N \). The \( i \)-th line describes junction \( i \): \((x_i, y_i, z_i)\) is the location of the \( i \)-th junction where the z-axis is the vertical axis; \( k_i \) indicates the number of open holes in the junction.

Each of the next \( M \) lines contains two integers \( a_j \) and \( b_j \) satisfying \(1 ≤ a_j < b_j ≤ N\). The \( j \)-th line indicates that pipe \( j \) connects junctions \( a_j \) and \( b_j \). At most one pipe connects any pair of junctions, and no two junctions share the same coordinates. The source is junction 1, and the destination is junction \( N \).

## Output

For each case, display the case number. Then if suitable new pipes and plugs can be used to construct the desired system, display the minimum cost of connecting the source junction to the destination junction, accurate to four decimal places. If it is impossible to connect the source to the destination, display the word `impossible`.

## Sample Input