SP9 DIRVS - Direct Visibility

Building the GSM network is a very expensive and complex task. Moreover, after the _Base Transceiver Stations_ (_BTS_) are built and working, we need to perform many various measurements to determine the state of the network, and propose effective improvements to be made. The ACM technicians have a special equipment for measuring the strength of electro-magnetic fields, the transceivers' power and quality of the signal. This equipment is packed into a huge knapsack and the technician must move with it from one BTS to another. Unfortunately, the knapsack have not enough memory for storing all of the measured values. It has a small cache only, that can store values for several seconds. Then the values must be transmitted to the BTS by an infrared connection (IRDA). The IRDA needs direct visibility between the technician and the BTS. Your task is to find the path between two neighbouring BTSes such that at least one of those BTSes is always visible.

There is a single positive integer T on the first line of input (equal to about 500). It stands for the number of test cases to follow. Each test case consists of a town description. For simplicity, a town is modelled as a rectangular grid of P x Q square fields. Each field is exactly 1 metre wide. For each field, a non-negative integer Z $ _{i,j} $ is given, representing the height of the terrain in that place, in metres. That means the town model is made of cubes, each of them being either solid or empty. There are no "half solid" cubes. The first line of each test case contains two integer numbers P and Q, separated by a single space, 1

You are to find the shortest possible path from BTS (R $ _{1} $ , C $ _{1} $ ) to BTS (R $ _{2} $ , C $ _{2} $ ), meeting the above criteria. All steps must be done between neighbouring fields, the terrain must not elevate or descend too much, and at the end of each step, at least one BTS must be visible. For each test case, print one line containing the sentence The shortest path is M steps long., where M is the number of steps that must be made. If there is no such path, output the sentence Mission impossible!.