Stack Machine

A stack machine is a special bus: it has a single door at the front, and it is so narrow that passengers cannot pass one another. The passenger who boards last must therefore be the first to get off, so the passengers behave like a stack (last in, first out).

The bus drives through a city whose intersections are connected by one-way roads. Driving along a road causes exactly one passenger to board or to get off. For each road the height of that passenger is fixed, and two passengers may have the same height.

A route is a sequence of roads the bus drives along. The bus must be empty at the start and at the end of the route, and whenever a passenger gets off it must be the passenger currently on top of the stack (whose height must equal the height fixed for that road). Plan routes between given intersections.

The first line contains the number of test cases $T$. Each test case begins with a line of three integers $N$, $M$, $Q$: the number of intersections ($1 \le N \le 100$), the number of roads ($1 \le M \le 100000$), and the number of queries ($1 \le Q \le 100000$). Intersections are numbered $1$ to $N$. The next $M$ lines each contain three integers $X$, $Y$, $Z$: a one-way road runs from intersection $X$ to intersection $Y$; if $Z > 0$ a passenger $Z$ centimetres tall boards, and if $Z < 0$ a passenger $-Z$ centimetres tall gets off. Every passenger height is between $40$ and $220$ centimetres. The next $Q$ lines each contain two integers, the start and end intersections of a route.

For each query, output on its own line the length (the number of roads) of the shortest non-empty route the bus can drive from the start intersection to the end intersection, beginning and ending empty. When such a route exists, its length is guaranteed to be at most $10^9$. If no such route exists, output the word impossible.