Trang trại của Farmer John có thể được biểu diễn bằng một đồ thị có hướng có trọng số, với các con đường (cạnh) nối các đỉnh và trọng số của mỗi cạnh là thời gian cần để đi qua con đường đó. Mỗi ngày, Bessie muốn đi từ chuồng (ở đỉnh $1$) đến cánh đồng (ở đỉnh $N$), đi qua đúng $K$ con đường, và muốn đến cánh đồng nhanh nhất có thể với điều kiện này. Tuy nhiên, đến một lúc nào đó, các con đường không còn được bảo trì và lần lượt bị hỏng, không thể đi qua nữa. Hãy giúp Bessie tìm đường đi ngắn nhất từ chuồng đến cánh đồng tại mọi thời điểm!

Cụ thể, ban đầu ta có một đồ thị có hướng đầy đủ có trọng số gồm $N$ đỉnh ($1\le N\le 300$) và $N^2$ cạnh: một cạnh cho mỗi cặp $(i, j)$ với $1 \le i, j \le N$ (lưu ý rằng có $N$ cạnh khuyên). Sau mỗi lần xóa, hãy xuất trọng số nhỏ nhất của một đường đi từ $1$ đến $N$ đi qua đúng $K$ cạnh (không nhất thiết phân biệt), với $2\le K\le 8$. Lưu ý rằng sau lần xóa thứ $i$, đồ thị còn $N^2-i$ cạnh.

Trọng số của một đường đi được định nghĩa là tổng trọng số của tất cả các cạnh trên đường đi đó. Lưu ý rằng một đường đi có thể đi qua cùng một cạnh hoặc cùng một đỉnh nhiều lần, kể cả các đỉnh $1$ và $N$.

Dữ liệu vào

Dòng đầu tiên chứa $N$ và $K$.

Mỗi dòng trong $N$ dòng tiếp theo chứa $N$ số nguyên. Số nguyên thứ $j$ trên dòng thứ $i$ là $w_{ij}$ ($1\le w_{ij}\le 10^8$).

Sau đó là $N^2$ dòng nữa, mỗi dòng chứa hai số nguyên $i$ và $j$ ($1\le i,j\le N$). Mỗi cặp số nguyên xuất hiện đúng một lần.

Dữ liệu ra

Xuất đúng $N^2$ dòng, mỗi dòng là trọng số nhỏ nhất của một đường đi gồm $K$ cạnh sau lần xóa tương ứng. Nếu không tồn tại đường đi gồm $K$ cạnh, hãy xuất $-1$.

Ví dụ

Dữ liệu vào 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

Dữ liệu ra 1

11
18
22
22
22
-1
-1
-1
-1

Ghi chú

Sau lần xóa đầu tiên, đường đi ngắn nhất gồm $4$ cạnh là:

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

Sau lần xóa thứ hai, đường đi ngắn nhất gồm $4$ cạnh là:

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

Sau lần xóa thứ ba, đường đi ngắn nhất gồm $4$ cạnh là:

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

Sau sáu lần xóa, không còn đường đi gồm $4$ cạnh.

Nhiệm vụ con

• Với $2\le T\le 14$, test thứ $T$ thỏa mãn $K=\lfloor (T+3)/2\rfloor$.

Tác giả bài toán: Benjamin Qi