如题，大体思路折半大力转移。

k<8 的都过了。

#include <bits/stdc++.h>
#define ll long long
#define int ll
#define pb push_back
using namespace std;
const int N=302;
const ll inf=(ll)(2e15);
pair<int,int>e[N*N];
vector<ll>vec;
ll v[N][N],d1[N][N],d2[N][N],d3s[N],d3t[N],d4s[N],d4t[N],ans;
int n,K;

void clr() {
	for(int i=0;i<=n;i++)
		for(int j=0;j<=n;j++)
			d1[i][j]=d2[i][j]=inf;
	for(int i=0;i<=n;i++) d3s[i]=d3t[i]=d4s[i]=d4t[i]=inf;
}

void add(int x,int y) {
	d1[x][y]=v[x][y];
	for(int a=1;a<=n;a++) {
		d2[a][y]=min(d2[a][y],d1[a][x]+d1[x][y]);
		d2[x][a]=min(d2[x][a],d1[x][y]+d1[y][a]);
	}
	if(x==1) {
		for(int c=1;c<=n;c++) d3s[c]=min(d3s[c],d1[x][y]+d2[y][c]);
		d3t[1]=min(d3t[1],d1[x][y]+d2[y][n]);
	}
	if(y==n) {
		for(int c=1;c<=n;c++) d3t[c]=min(d3t[c],d2[c][x]+d1[x][y]);
		d3s[n]=min(d3s[n],d2[1][x]+d1[x][y]);
	}
	for(int c=1;c<=n;c++) {
		d3s[y]=min(d3s[y],d1[1][c]+d1[c][x]+d1[x][y]);
		d3s[c]=min(d3s[c],d1[1][x]+d1[x][y]+d1[y][c]);
		d3t[x]=min(d3t[x],d1[x][y]+d1[y][c]+d1[c][n]);
		d3t[c]=min(d3t[c],d1[c][x]+d1[x][y]+d1[y][n]);
		
		d3s[c]=min(d3s[c],min(d2[1][x]+d1[x][c],d1[1][x]+d2[x][c]));
		d3s[c]=min(d3s[c],min(d2[1][y]+d1[y][c],d1[1][y]+d2[y][c]));
		
		d3t[c]=min(d3t[c],min(d1[c][x]+d2[x][n],d2[c][x]+d1[x][n]));
		d3t[c]=min(d3t[c],min(d1[c][y]+d2[y][n],d2[c][y]+d1[y][n]));
		
		d3s[y]=min(d3s[y],min(d1[1][c]+d2[c][y],d2[1][c]+d1[c][y]));
		d3t[y]=min(d3t[y],min(d1[y][c]+d2[c][n],d2[y][c]+d1[c][n]));
		
		d3s[x]=min(d3s[x],min(d1[1][c]+d2[c][x],d2[1][c]+d1[c][x]));
		d3t[x]=min(d3t[x],min(d1[x][c]+d2[c][n],d2[x][c]+d1[c][n]));
	}
	if(x==1) {
		d4t[1]=min(d4t[1],d1[x][y]+d3t[y]);
	}
	if(y==n) {
		d4s[n]=min(d4s[n],d3s[x]+d1[x][y]);
	}
	for(int c=1;c<=n;c++) {
		d4s[c]=min(d4s[c],d1[1][x]+d1[x][y]+d2[y][c]);
		d4s[c]=min(d4s[c],d2[1][x]+d1[x][y]+d1[y][c]);
		d4s[c]=min(d4s[c],d3s[y]+d1[y][c]);
		d4s[c]=min(d4s[c],d3s[x]+d1[x][c]);
		d4s[c]=min(d4s[c],d2[1][x]+d2[x][c]);
		d4s[c]=min(d4s[c],d2[1][y]+d2[y][c]);
		
		d4s[y]=min(d4s[y],d2[1][c]+d1[c][x]+d1[x][y]);
		d4s[y]=min(d4s[y],d3s[x]+d1[x][y]);
		d4s[y]=min(d4s[y],d3s[c]+d1[c][y]);
		d4s[y]=min(d4s[y],d2[1][c]+d2[c][y]);
		d4s[y]=min(d4s[y],d3s[x]+d1[x][y]);
		
		d4s[x]=min(d4s[x],d3s[c]+d1[c][x]);
		d4s[x]=min(d4s[x],d2[1][c]+d2[c][x]);
		
		d4t[x]=min(d4t[x],d1[x][y]+d2[y][c]+d1[c][n]);
		d4t[x]=min(d4t[x],d1[x][y]+d3t[y]);
		d4t[x]=min(d4t[x],d1[x][c]+d3t[c]);
		d4t[x]=min(d4t[x],d2[x][c]+d2[c][n]);
		
		d4t[y]=min(d4t[y],d2[y][c]+d2[c][n]);
		d4t[y]=min(d4t[y],d1[y][c]+d3t[c]);
		
		d4t[c]=min(d4t[c],d1[c][x]+d1[x][y]+d2[y][n]);
		d4t[c]=min(d4t[c],d2[c][x]+d1[x][y]+d1[y][n]);
		d4t[c]=min(d4t[c],d1[c][x]+d3t[x]);
		d4t[c]=min(d4t[c],d1[c][y]+d3t[y]);
		d4t[c]=min(d4t[c],d2[c][x]+d2[x][n]);
		d4t[c]=min(d4t[c],d2[c][y]+d2[y][n]);
	}
}

signed main() {
//	freopen("5.in","r",stdin); freopen("xgf.out","w",stdout);
	cin.tie(0); ios::sync_with_stdio(false);
	cin>>n>>K;
	clr();
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			cin>>v[i][j];
	for(int i=1;i<=n*n;i++) cin>>e[i].first>>e[i].second;
	vec.pb(-1);
	for(int i=n*n;i>=2;i--) {
		add(e[i].first,e[i].second);
		if(K==2) {
			ans=d2[1][n];
			for(int a=1;a<=n;a++) ans=min(ans,d1[1][a]+d1[a][n]);
		}
		else if(K==3) {
			ans=min(d3s[n],d3t[1]);
			for(int a=1;a<=n;a++) ans=min(ans,min(d1[1][a]+d2[a][n],d2[1][a]+d1[a][n]));
		}
		else if(K==4) {
			ans=min(d4s[n],d4t[1]);
			for(int a=1;a<=n;a++) ans=min(ans,min(d2[1][a]+d2[a][n],min(d3s[a]+d1[a][n],d1[1][a]+d3t[a])));
		}
		else if(K==5) {
			ans=inf;
			for(int a=1;a<=n;a++) ans=min(ans,min(d3s[a]+d2[a][n],min(d4s[a]+d1[a][n],min(d1[1][a]+d4t[a],d2[1][a]+d3t[a]))));
		} else if(K==6) {
			ans=inf;
			for(int a=1;a<=n;a++) ans=min(ans,min(d3s[a]+d3t[a],min(d2[1][a]+d4t[a],d4s[a]+d2[a][n])));
		} else if(K==7) {
			ans=inf;
			for(int a=1;a<=n;a++) ans=min(ans,min(d3s[a]+d4t[a],d4s[a]+d3t[a]));
		} else {
			ans=inf;
			for(int a=1;a<=n;a++) ans=min(ans,d4s[a]+d4t[a]);
		}
		if(ans<inf) vec.pb(ans);
		else vec.pb(-1);
	}
	reverse(vec.begin(),vec.end());
	for(ll x:vec) cout<<x<<'\n';
	return 0;
}