【题目描述】

**注意：本题的时间限制为 3 秒，比通常限制高 50%。**

Farmer John 的农场可以用一个带权有向图表示，道路（边）连接不同的结点，每条边的权值是通过道路所需的时间。每天，Bessie 喜欢从牛棚（位于结点 1）经过恰好 K 条道路前往草地（位于结点 N），并希望在此限制下尽快到达草地。然而，在某些时候，道路停止维护，一条一条地开始破损，变得无法通行。帮助 Bessie 求出每一时刻从牛棚到草地的最短路径！

形式化地说，我们从一个 N 个结点（1≤N≤300）和 N^2 条边的带权有向完全图开始：对于 1≤i,j≤N 的每一对 (i,j) 存在一条边（注意存在 N 个自环）。每次移除一条边后，输出从 1 到 N 的所有路径中经过恰好 K 条边（不一定各不相同）的路径的最小权值（2≤K≤8）。注意在第 i 次移除后，该图还剩下N^2−i 条边。

路径的权值定义为路径上所有边的权值之和。注意一条路径可以包含同一条边多次或同一个结点多次，包括结点 1 和 N。

【输入格式】（从终端 / 标准输入读入）：

输入的第一行包含 N 和 K。

以下 N 行每行包含 N 个整数。第 i 行的第 j 个整数为 wij（1≤wij≤10^8）。

以下 N^2 行，每行包含两个整数 i 和 j（1≤i,j≤N）。每对整数出现恰好一次。

【输出格式】（输出至终端 / 标准输出）：

输出 N^2 行，为每一次移除后经过 K 条边的路径的最小权值。如果不存在经过 K 条边的路径则输出 −1。

【输入样例】：

3 4

10 4 4

9 5 3

2 1 6

3 1

2 3

2 1

3 2

2 2

1 3

3 3

1 1

1 2

【输出样例】：

11

18

22

22

22

-1

-1

-1

-1

【样例说明】

第一次移除后，最短的经过 4 条边的路径为：

1 -> 2 -> 3 -> 2 -> 3

第二次移除后，最短的经过 4 条边的路径为：

1 -> 3 -> 2 -> 1 -> 3

第三次移除后，最短的经过 4 条边的路径为：

1 -> 3 -> 3 -> 3 -> 3

六次移除后，不再存在经过 4 条边的路径。

【测试点性质】：

对于2≤T≤14，测试点 T 满足 K=⌊(T+3)/2⌋。