Exact K-Edge Paths with Edge Removals

Farmer John's farm can be represented as a weighted directed graph with \(N\) nodes and \(N^2\) edges. Each directed edge from node \(i\) to node \(j\) has an associated travel time (note that self-loops are included). Every day, Bessie starts at the barn (node \(1\)) and wants to reach the field (node \(N\)) by traversing exactly \(K\) roads, minimizing the overall travel time.

However, due to poor maintenance, the roads (edges) begin to fail and are removed one by one. After each removal, your task is to determine the minimum total travel time needed to travel from node \(1\) to node \(N\) using exactly \(K\) edges. A path can use the same edge or node multiple times (nodes \(1\) and \(N\) may appear more than once in the path). If no such path exists after a removal, output -1.

The weight of a path is defined as the sum of the weights of its edges.

inputFormat

The first line contains three integers \(N\), \(K\) and \(R\), where \(1 \leq N \leq 300\), \(2 \leq K \leq 8\) and \(R\) is the number of edges to be removed.

The next \(N\) lines each contain \(N\) integers. The \(j\)-th integer on the \(i\)-th line represents the weight of the edge from node \(i\) to node \(j\).

The following \(R\) lines each contain two integers \(u\) and \(v\), indicating that the edge from node \(u\) to node \(v\) is removed at that step. It is guaranteed that each edge is removed at most once.

outputFormat

Output \(R\) lines. The \(i\)-th line should contain a single integer representing the minimum total travel time of any path from node \(1\) to node \(N\) that uses exactly \(K\) edges after the first \(i\) removals. If no such path exists, output -1.

sample

3 2 2
0 1 5
2 0 3
4 6 0
1 2
2 3

5
5