{"raw_statement":[{"iden":"statement","content":"Farmer John 的农场可以用一个带权有向图表示，道路（边）连接不同的结点，每条边的权值是通过道路所需的时间。每天，Bessie 喜欢从牛棚（位于结点 $1$）经过恰好 $K$ 条道路前往草地（位于结点 $N$），并希望在此限制下尽快到达草地。然而，在某些时候，道路停止维护，一条一条地开始破损，变得无法通行。帮助 Bessie 求出每一时刻从牛棚到草地的最短路径！\n\n形式化地说，我们从一个 $N$ 个结点（$1 \\le N \\le 300$）和 $N^2$ 条边的带权有向完全图开始：对于 $1 \\le i,j \\le N$ 的每一对 $(i,j)$ 存在一条边（注意存在 $N$ 个自环）。每次移除一条边后，输出从 $1$ 到 $N$ 的所有路径中经过恰好 $K$ 条边（不一定各不相同）的路径的最小权值（$2 \\le K \\le 8$）。注意在第 $i$ 次移除后，该图还剩下 $N^2-i$ 条边。\n\n路径的权值定义为路径上所有边的权值之和。注意一条路径可以包含同一条边多次或同一个结点多次，包括结点 $1$\n和 $N$。"},{"iden":"input","content":"输入的第一行包含 $N$ 和 $K$。\n\n以下 $N$ 行每行包含 $N$ 个整数。第 $i$ 行的第 $j$ 个整数为 $w_{ij}(1 \\le w_{ij} \\le 10^8)$。\n\n以下 $N^2$ 行，每行包含两个整数 $i$ 和 $j$（$1 \\le i,j \\le N$）。每对整数出现恰好一次。 "},{"iden":"output","content":"输出 $N^2$ 行，为每一次移除后经过 $K$ 条边的路径的最小权值。如果不存在经过 $K$ 条边的路径则输出 $-1$。 "},{"iden":"note","content":"### 样例 1 解释\n\n第一次移除后，最短的经过 $4$ 条边的路径为：\n\n$$1 \\rightarrow 2 \\rightarrow 3 \\rightarrow 2 \\rightarrow 3$$\n\n第二次移除后，最短的经过 $4$ 条边的路径为：\n\n$$1 \\rightarrow 3 \\rightarrow 2 \\rightarrow 1 \\rightarrow 3$$\n\n第三次移除后，最短的经过 $4$ 条边的路径为：\n\n$$1 \\rightarrow 3 \\rightarrow 3 \\rightarrow 3 \\rightarrow 3$$\n\n六次移除后，不再存在经过 $4$ 条边的路径。 \n\n### 测试点性质\n\n - 对于 $2 \\le T \\le 14$，测试点 $T$ 满足 $K=\\lfloor \\dfrac{T+3}{2} \\rfloor$。 "}],"translated_statement":null,"sample_group":[["3 4\n10 4 4\n9 5 3\n2 1 6\n3 1\n2 3\n2 1\n3 2\n2 2\n1 3\n3 3\n1 1\n1 2","11\n18\n22\n22\n22\n-1\n-1\n-1\n-1"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}