### 问题描述 小齐居住在一座由道路连接的有向加权图中的农场，每条道路的权重表示沿着这条道路行进所需的时间。每天，小齐都喜欢从谷仓（位于节点 $1$）到田地（位于节点 $N$）出行，但她有一个特殊的要求：她想要在保证经过 $K$ 条边的情况下尽快到达目的地。然而，道路在某一时刻停止维护，一条接一条地损坏，变得无法通行。请帮助小齐找到从谷仓到田地的最短路径，并在每次道路损坏后输出路径的最小权重。 具体而言，我们从一个包含N个节点的完全加权有向图开始，有N^2条边：对于$1 \leq i, j \leq N$的每一对（$i，j$）都有一条边（注意，有 $N$ 个自环边）。每次移除一条边后，输出经过恰好 $K$ 条边（不一定是不同的）的从 $1$ 到 $N$ 的路径的最小权重。注意，在第i次移除后，图中将剩下 $N^2-i$ 条边。 路径的权重定义为路径上所有边的权重之和。请注意，路径中可以包含多条相同的边和多个相同的节点，包括节点 $1$ 和 $N$。 ### 输入格式 第一行包含两个整数 $N$ 和 $K$。 接下来的N行，每行包含N个整数，第i行的第j个整数为$w_{ij}$（$1 \leq w_{ij} \leq 10^8$），表示从节点i到节点j的边的权重。 然后是 $N^2$ 额外的行，每行包含两个整数i和j（$1 \leq i, j \leq N$）。每一对整数恰好出现一次。 ### 输出格式 输出恰好 $N^2$ 行，分别表示每次移除一条边后从 $1$ 到 $N$ 的路径的最小权重。如果不存在经过 $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 ``` ### 评测数据规模 $1 \leq N \leq 300$，$2 \leq K \leq 8$。