Given an undirected weighted graph with negative weights, it is necessary to output information about the shortest path between 2 vertices.
Input
The first line contains an integer n - the number of vertices in the graph. Next, the input is an adjacency matrix, in which -1 means the absence of an edge between the vertices. After the matrix there is a number k - the number of requests, the next k lines contain 2 numbers each, a and b - vertices in request.
Imprint
The string must contain k numbers - the distance between a pair of numbers from the query in the order they are entered, if it is impossible to get from the top a to the top b, then output Imp.
Examples
| # |
Input |
Output |
| 1 |
3
0 3 -1
3 0 4
-1 4 0
3
1 3
3 2
1 2
|
7
4
3 |