\(\textbf{This is an approximate probem}\).

Given an undirected complete graph G with n vertices. The weight of the edge between \((i,j)\) is equal to \(C[i][j]\). Let \(D(i,j)\) be the shortest distance between vertices \(i,j\) and \(W(G)\) be the sum of all shortest distances between any two vertices. You can remove at most k edges from graph G in order to obtain a graph G'. You have to maximize the ratio of the sum of all shortest distances between any two vertices in new graph G' (after removing the edges) and sum of all shortest distances between any two vertices in old graph G (before reomoving the edges): \(\frac{W(G')}{W(G)}\). G must remain connected.

\(\textbf{Input}\)

The first line contains two space separated integers n \((n = 128)\) and k \((0 \le k \le (n - 1) ^ 2)\) denoting the number of vertices and at most how many edges you can remove.

Next n lines contains n space separated integers. \(i^{th}\) line denotes the elements of \(C[i]\) i.e.

\(C[i][1], C[i][2], \dots, C[i][n]\) \((C[i][i] = 0, C[i][j] = C[j][i], 1 \le C[i][j] \le 2^{20})\).

\(\textbf{Output}\)

The first line contains a number q \((0 \le q \le k)\) - the number of edges deleted.

Next q lines contains two space separated integers each, \(x_i, y_i\) \((1 \le x_i < y_i \le n)\) denoting that edge \((x_i, y_i)\) will be deleted.

\(\textbf{Scoring}\)

The score will be equal to \(\frac{W(G')}{W(G)}\).

\(\textbf{Tests}\)

The value k will be taken uniformly from interval \([0, (n - 1) ^ 2]\).

The value \(C[i][j]\) \((1 \le i < j \le n)\) will be taken uniformly from interval \([1, 2^{20}]\).