Stack Machine

A mathematician observes one person get on a bus. Then two people get off the bus. The mathematician says: "If one more person gets on the bus, the bus will be empty."

A stack machine is a special kind of bus. It only has doors at the front, and it is so narrow that the people on the bus cannot move past each other. Of the people on the bus, the person who got on the bus last must be the first to get off.

The bus travels in a city in which roads connect intersections, and all the roads are unidirectional. Along each road, a person either gets on or off the bus.

The mathematician does not know the identity of the bus passengers, but can estimate their height. Note that there may be multiple people with the same height.

Your task is to plan the route of the bus. The bus must be empty at the beginning and end of the route. Along the route, it must pick up and drop off the people corresponding to the roads it travels on. The height of the person that gets on or off the bus is fixed for each road.

The first line of input contains a single integer, the number of test cases to follow. Each test case begins with a line containing three integers N, M, Q, the number of intersections and roads in the city and the number of queries, respectively. The number of intersections is between 1 and 100, inclusive. The number of roads and the number of queries are each between 1 and 100000, inclusive. Intersections in the city are numbered from 1 to N. The first line of each test case is followed by M lines describing the roads. Each of these lines contains three integers X, Y, and Z. These integers indicate that a road exists from intersection X to intersection Y, and that when the bus travels on this road, a person who is Z centimetres tall gets on the bus, if Z is positive, or a person who is -Z centimetres tall gets off the bus, if Z is negative. For example, Z=170 indicates that a 170 cm tall person gets on the bus, and Z=-170 indicates that a 170 cm tall person gets off the bus. Each person is at least 40 cm and at most 220 cm tall. The lines describing the roads are followed by Q more lines, each describing a query. A line describing a query contains two integers, the beginning and ending intersections of the bus route.

For each query, output a line containing a single integer giving the length of the shortest non-empty path that the bus can take from the beginning to the end of the route. The input data will be such that this length is no more than 10^9. If there is no such path, output a line containing the word impossible.

1
2 2 4
1 2 100
2 1 -100
1 1
2 2
1 2
2 1

2
impossible
impossible
impossible

University of Waterloo Local Contest 2010.07.10