double TL = 1.95;
//#pragma GCC optimize("O3,Ofast,omit-frame-pointer,unroll-all-loops,tree-loop-vectorize,tree-slp-vectorize")
#include <algorithm>
#include <chrono>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <unordered_map>
#include <vector>

int STANDARD = 1;
using namespace std;
#define F0(i,n) for (int i=0; i<(n); i++)
#define F1(i,n) for (int i=1; i<=(n); i++)
#define CL(a,x) memset(x, a, sizeof(x));
#define SZ(x) ((int)x.size())
const int inf = 1000000000;
const double pi = acos(-1.0);
typedef pair<int, int> pii;
typedef long long ll;
const double EPS = 1e-9;
istream& operator>>(istream& is, pii& p) { is>>p.first>>p.second; return is; }
template<class A, class B>
ostream& operator<<(ostream& os, const pair<A, B>& p) { os << "(" << p.first << "," << p.second << ")"; return os; }
template<class A, class B, class C>
ostream& operator<<(ostream& os, const tuple<A, B, C>& p) { os << "(" << get<0>(p) << "," << get<1>(p) << "," << get<2>(p) << ")"; return os; }
template<class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
    os << "["; F0(i,SZ(v)) { if (i>0) os << ","; os << v[i]; } os << "]"; return os;
}
template<class T>
ostream& operator<<(ostream& os, const set<T>& v) {
    os << "{"; int f=1; for(auto i:v) { if(f)f=0;else os << ","; cerr << i; } os << "}"; return os;
}
template<class T, class R>
ostream& operator<<(ostream& os, const map<T,R>& v) {
    os << "{"; int f=1; for(auto i:v) { if(f)f=0;else os << ", "; cerr << i.first << ":" << i.second; } os << "}"; return os;
}
void print_all() { cerr << endl; }
template <typename H, typename... T>
void print_all(H head, T... tail) { cerr << " " << head; print_all(tail...); }

chrono::system_clock::time_point init_time = chrono::system_clock::now();
inline double GetSeconds() {
    chrono::system_clock::time_point current_time = chrono::system_clock::now();
    double ret = chrono::duration_cast<std::chrono::nanoseconds>(current_time - init_time).count();
    return ret * 1e-9;
}

const int MAX_RAND = 1 << 30;
struct Rand {
    ll x, y, z, w, o;
    Rand() { throw; }
    Rand(ll seed) { reseed(seed); o = 0; }
    inline void reseed(ll seed) { x = 0x498b3bc5 ^ seed; y = 0; z = 0; w = 0;  F0(i, 20) mix(); }
    inline void mix() { ll t = x ^ (x << 11); x = y; y = z; z = w; w = w ^ (w >> 19) ^ t ^ (t >> 8); }
    inline ll rand() { mix(); return x & (MAX_RAND - 1); }
    inline ll zh() { mix(); return x; }
    inline int nextInt(int n) { return rand() % n; }
    inline int nextInt(int L, int R) { return rand()%(R - L + 1) + L; }
    inline int nextBool() { if (o < 4) o = rand(); o >>= 2; return o & 1; }
    inline double nextDouble() { return rand() * 1.0 / MAX_RAND; }
    inline double nextDouble(double L, double R) { return L + (R - L) * nextDouble(); }
    template<class T> auto REL(T& v) { return v[nextInt(SZ(v))]; }
    template<class T> void RS(vector<T>& v) { F1(i, SZ(v)-1) { int j = nextInt(0, i); swap(v[i], v[j]); } }
    int ws_n; vector<double> ws_prob; vector<int> ws_alias;
    inline void PrepareWeightedSample(const vector<double>& p) {
        ws_n = SZ(p); ws_prob.assign(ws_n, 0); ws_alias.assign(ws_n, 0);
        vector<double> sc(ws_n);
        vector<int> small, large;
        double sum = 0; F0(i, ws_n) sum += p[i];
        F0(i, ws_n) {
            sc[i] = p[i]/sum * ws_n; if (sc[i] < 1) small.push_back(i); else large.push_back(i);
        }
        while(!small.empty() && !large.empty()){
            int l = small.back(); small.pop_back();
            int g = large.back(); large.pop_back();
            ws_prob[l] = sc[l]; ws_alias[l] = g;
            sc[g] = sc[g] - (1 - sc[l]);
            if(sc[g] < 1) small.push_back(g); else large.push_back(g);
        }
        for(int g : large){ ws_prob[g]=1; ws_alias[g]=g; }
        for(int l : small){ ws_prob[l]=1; ws_alias[l]=l; }
    }
    inline int WeightedSample() { int i = nextInt(ws_n); return nextDouble() < ws_prob[i] ? i : ws_alias[i]; }
};
Rand my(2023);
double saveTime;
double t_o[20];
ll c_o[20];
void Init() {
    saveTime = GetSeconds();
    F0(i, 20) t_o[i] = 0.0;
    F0(i, 20) c_o[i] = 0;
}
double Elapsed() { return GetSeconds() - saveTime; }
void Report() {
    double tmp = Elapsed();
    cerr << "-------------------------------------" << endl;
    cerr << "Elapsed time: " << tmp << " sec" << endl;
    double total = 0.0; F0(i, 20) { if (t_o[i] > 0) cerr << "t_o[" << i << "] = " << t_o[i] << endl; total += t_o[i]; } cerr << endl; //if (total > 0) cerr << "Total spent: " << total << endl;
    F0(i, 20) if (c_o[i] > 0) cerr << "c_o[" << i << "] = " << c_o[i] << endl;
    cerr << "-------------------------------------" << endl;
}

#ifdef LOCAL
#define PR(...) cerr << #__VA_ARGS__ << " =", print_all(__VA_ARGS__)
struct AutoTimer {
    int x;
    double t;
    AutoTimer(int x) : x(x) { t = Elapsed(); }
    ~AutoTimer() { t_o[x] += Elapsed() - t; }
};
#define AT(i) AutoTimer _a##i(i)
#else
//#pragma GCC target("avx2")
#pragma GCC optimize("O3,unroll-all-loops")
#define PR(...)
#define AT(i)
#endif

// CONSTANTS
const int N = 50;
int n, k;
int d[N][N];
int W[N][N];
double bscore, score;
vector<pii> bsol, sol;
double initial_score;
vector<pii> initial_sol;
const int SAMPLES = 25;
const int di[4] = {-1, 1, 0, 0};
const int dj[4] = {0, 0, -1, 1};
bool cut[N*N];
unsigned char dry[SAMPLES][N*N];
unsigned long long dry_rows[SAMPLES][N];
int adj[N*N][4], deg[N*N], uncut_pos[N*N];
vector<pii> trees, uncut;
vector<int> uncut_bucket[10];
int bucket_pos[N*N], uncut_weight;

// Exact component cache for the committed cut set, separately for every sample.
int comp_id[SAMPLES][N*N], comp_size[SAMPLES][N*N];
int comp_head[SAMPLES][N*N], comp_tail[SAMPLES][N*N];
int comp_next[SAMPLES][N*N], comp_prev[SAMPLES][N*N];
vector<int> free_comp[SAMPLES];
ll cached_loss, proposed_loss;
int split_mode[SAMPLES], split_count[SAMPLES];
int split_nodes[SAMPLES][N*N], split_part[SAMPLES][N*N];
int split_end[SAMPLES][4], split_size[SAMPLES][4];
unsigned int visit_stamp, visited[N*N], target[N*N];

const int LOGN = 1 << 16;
double logs[LOGN];

template<class T> T sqr(T x) { return x*x; }

void AddToBucket(int v) {
    int w = d[v/n][v%n];
    bucket_pos[v] = SZ(uncut_bucket[w]);
    uncut_bucket[w].push_back(v);
    uncut_weight += w*w;
}

void RemoveFromBucket(int v) {
    int w = d[v/n][v%n], p = bucket_pos[v];
    int last = uncut_bucket[w].back();
    uncut_bucket[w][p] = last;
    bucket_pos[last] = p;
    uncut_bucket[w].pop_back();
    bucket_pos[v] = -1;
    uncut_weight -= w*w;
}

int RandomUncut() {
    int ticket = my.nextInt(uncut_weight), w = 1;
    for (; w < 9; w++) {
        int weight = w*w * SZ(uncut_bucket[w]);
        if (ticket < weight) break;
        ticket -= weight;
    }
    int v = uncut_bucket[w][my.nextInt(SZ(uncut_bucket[w]))];
    return uncut_pos[v];
}

ll SampleLoss(const unsigned char* sample, const bool* cuts) {
    ll total = 0;
    unsigned char used[N*N];
    int q[N*N];
    F0(v, n*n) used[v] = cuts[v] || !sample[v];
    F0(v, n*n) if (!used[v]) {
        int head = 0, tail = 0;
        used[v] = 1;
        q[tail++] = v;
        while (head < tail) {
            int x = q[head++];
            F0(t, deg[x]) {
                int y = adj[x][t];
                if (!used[y]) {
                    used[y] = 1;
                    q[tail++] = y;
                }
            }
        }
        total += 1LL * tail * tail;
    }
    return total;
}

ll RowSampleLoss(const unsigned long long* active) {
    int parent[N*N], size[N*N];
    auto root = [&](int v) {
        while (parent[v] != v) {
            parent[v] = parent[parent[v]];
            v = parent[v];
        }
        return v;
    };
    ll total = 0;
    unsigned long long prev = 0;
    F0(i, n) {
        unsigned long long remaining = active[i];
        int base = i*n;
        // Initialize each horizontal run as a component, then join vertical overlaps.
        while (remaining) {
            int j = __builtin_ctzll(remaining);
            int len = __builtin_ctzll(~(remaining >> j));
            int r = base+j;
            F0(t, len) parent[r+t] = r;
            size[r] = len;
            total += len*len;
            remaining &= ~(((1ULL << len)-1) << j);
        }
        unsigned long long both = prev & active[i];
        unsigned long long starts = both & ~(both << 1);
        while (starts) {
            int j = __builtin_ctzll(starts);
            starts &= starts-1;
            int a = root(base-n+j), b = root(base+j);
            if (a == b) continue;
            if (size[a] < size[b]) swap(a, b);
            total += 2LL*size[a]*size[b];
            parent[b] = a;
            size[a] += size[b];
        }
        prev = active[i];
    }
    return total;
}

double Evaluate() {
    unsigned long long cut_rows[N] = {}, active[N];
    F0(i, n) F0(j, n) cut_rows[i] |= (unsigned long long)cut[i*n+j] << j;
    ll total = 0;
    F0(s, SAMPLES) {
        F0(i, n) active[i] = dry_rows[s][i] & ~cut_rows[i];
        total += RowSampleLoss(active);
    }
    return total / (1.0 * SAMPLES * n * n);
}

void InitComponents() {
    cached_loss = 0;
    CL(-1, comp_id);
    CL(0, comp_size);
    CL(-1, comp_head);
    CL(-1, comp_tail);
    CL(-1, comp_next);
    CL(-1, comp_prev);
    CL(0, visited);
    CL(0, target);
    visit_stamp = 0;
    int q[N*N];
    F0(s, SAMPLES) {
        free_comp[s].clear();
        int count = 0;
        F0(v, n*n) if (dry[s][v] && !cut[v] && comp_id[s][v] < 0) {
            int id = count++, head = 0, tail = 0;
            q[tail++] = v;
            comp_id[s][v] = id;
            while (head < tail) {
                int x = q[head++];
                F0(t, deg[x]) {
                    int y = adj[x][t];
                    if (dry[s][y] && !cut[y] && comp_id[s][y] < 0) {
                        comp_id[s][y] = id;
                        q[tail++] = y;
                    }
                }
            }
            comp_head[s][id] = q[0];
            comp_tail[s][id] = q[tail-1];
            comp_size[s][id] = tail;
            F0(t, tail) {
                comp_prev[s][q[t]] = t ? q[t-1] : -1;
                comp_next[s][q[t]] = t+1 < tail ? q[t+1] : -1;
            }
            cached_loss += 1LL*tail*tail;
        }
        for (int id = n*n-1; id >= count; id--) free_comp[s].push_back(id);
    }
}

double EvaluateSwap(int a, int b) {
    proposed_loss = cached_loss;
    F0(s, SAMPLES) {
        split_mode[s] = 0;
        split_count[s] = 0;
        int removed = comp_id[s][b];
        ll delta = 0;
        if (removed >= 0) {
            split_mode[s] = 1; // Removal leaves one component (possibly empty).
            int old_size = comp_size[s][removed];
            delta = 1-2LL*old_size;
            int nb[4], nn = 0;
            F0(t, deg[b]) {
                int v = adj[b][t];
                if (comp_id[s][v] == removed) nb[nn++] = v;
            }
            if (nn > 1) {
                if (++visit_stamp == 0) {
                    CL(0, visited);
                    CL(0, target);
                    visit_stamp = 1;
                }
                unsigned int stamp = visit_stamp;
                F0(t, nn) target[nb[t]] = stamp;
                int* q = split_nodes[s];
                int head = 0, tail = 1, remaining = nn-1;
                q[0] = nb[0];
                visited[nb[0]] = stamp;
                split_part[s][nb[0]] = 0;
                // Once all neighbors of b are connected without b, no split is possible.
                while (head < tail && remaining) {
                    int v = q[head++];
                    F0(t, deg[v]) {
                        int u = adj[v][t];
                        if (u == b || comp_id[s][u] != removed || visited[u] == stamp) continue;
                        visited[u] = stamp;
                        split_part[s][u] = 0;
                        q[tail++] = u;
                        if (target[u] == stamp) remaining--;
                    }
                }
                if (remaining) {
                    // The first fragment was exhausted; enumerate the remaining fragments.
                    split_mode[s] = 2;
                    split_count[s] = 1;
                    split_end[s][0] = tail;
                    split_size[s][0] = tail;
                    F0(t, nn) if (visited[nb[t]] != stamp) {
                        int part = split_count[s]++, start = tail;
                        q[tail++] = nb[t];
                        visited[nb[t]] = stamp;
                        split_part[s][nb[t]] = part;
                        head = start;
                        while (head < tail) {
                            int v = q[head++];
                            F0(z, deg[v]) {
                                int u = adj[v][z];
                                if (u == b || comp_id[s][u] != removed || visited[u] == stamp) continue;
                                visited[u] = stamp;
                                split_part[s][u] = part;
                                q[tail++] = u;
                            }
                        }
                        split_end[s][part] = tail;
                        split_size[s][part] = tail-start;
                    }
                    delta = -1LL*old_size*old_size;
                    F0(t, split_count[s]) delta += 1LL*split_size[s][t]*split_size[s][t];
                }
            }
        }
        if (dry[s][a]) {
            int groups[4], ng = 0;
            ll merged = 1, separate = 0;
            F0(t, deg[a]) {
                int v = adj[a][t], id = comp_id[s][v];
                if (v == b || id < 0) continue;
                int key = id, size = comp_size[s][id];
                if (id == removed) {
                    if (split_mode[s] == 2) {
                        int part = split_part[s][v];
                        key = n*n+part;
                        size = split_size[s][part];
                    } else size--;
                }
                bool seen = false;
                F0(j, ng) if (groups[j] == key) seen = true;
                if (seen) continue;
                groups[ng++] = key;
                merged += size;
                separate += 1LL*size*size;
            }
            delta += merged*merged-separate;
        }
        proposed_loss += delta;
    }
    return proposed_loss / (1.0*SAMPLES*n*n);
}

void MergeComponents(int s, int a, int b) {
    if (a == b) return;
    if (comp_size[s][a] < comp_size[s][b]) swap(a, b);
    for (int v = comp_head[s][b]; v >= 0; v = comp_next[s][v]) comp_id[s][v] = a;
    comp_next[s][comp_tail[s][a]] = comp_head[s][b];
    comp_prev[s][comp_head[s][b]] = comp_tail[s][a];
    comp_tail[s][a] = comp_tail[s][b];
    comp_size[s][a] += comp_size[s][b];
    comp_head[s][b] = comp_tail[s][b] = -1;
    comp_size[s][b] = 0;
    free_comp[s].push_back(b);
}

void AcceptSwap(int a, int b) {
    F0(s, SAMPLES) {
        int removed = comp_id[s][b];
        if (removed >= 0) {
            if (split_mode[s] == 2) {
                int start = 0;
                F0(part, split_count[s]) {
                    int id = removed;
                    if (part) { id = free_comp[s].back(); free_comp[s].pop_back(); }
                    int end = split_end[s][part];
                    comp_head[s][id] = split_nodes[s][start];
                    comp_tail[s][id] = split_nodes[s][end-1];
                    comp_size[s][id] = end-start;
                    for (int p = start; p < end; p++) {
                        int v = split_nodes[s][p];
                        comp_id[s][v] = id;
                        comp_prev[s][v] = p > start ? split_nodes[s][p-1] : -1;
                        comp_next[s][v] = p+1 < end ? split_nodes[s][p+1] : -1;
                    }
                    start = end;
                }
            } else {
                int prev = comp_prev[s][b], next = comp_next[s][b];
                if (prev >= 0) comp_next[s][prev] = next;
                else comp_head[s][removed] = next;
                if (next >= 0) comp_prev[s][next] = prev;
                else comp_tail[s][removed] = prev;
                if (--comp_size[s][removed] == 0) free_comp[s].push_back(removed);
            }
            comp_id[s][b] = comp_next[s][b] = comp_prev[s][b] = -1;
        }
        if (dry[s][a]) {
            int id = free_comp[s].back(); free_comp[s].pop_back();
            comp_id[s][a] = id;
            comp_head[s][id] = comp_tail[s][id] = a;
            comp_size[s][id] = 1;
            comp_prev[s][a] = comp_next[s][a] = -1;
            F0(t, deg[a]) {
                int v = adj[a][t];
                if (comp_id[s][v] >= 0) MergeComponents(s, comp_id[s][a], comp_id[s][v]);
            }
        }
    }
    cached_loss = proposed_loss;
}

void TraceScores() {
    const int ACTUAL_SAMPLES = 40000;
    bool initial_cut[N*N] = {}, final_cut[N*N] = {};
    for (pii p : initial_sol) initial_cut[p.first*n+p.second] = true;
    for (pii p : bsol) final_cut[p.first*n+p.second] = true;

    // Match sample_seed(), splitmix64(), and fill_dry() in the official tools.
    using ull = unsigned long long;
    ull state = 1469598103934665603ULL;
    ull threshold[N*N+1] = {};
    F0(i, n) F0(j, n) {
        state ^= '0' + d[i][j];
        state *= 1099511628211ULL;
        threshold[i*n+j] = (ull)(d[i][j] * (4294967296.0 / 10.0));
    }
    state ^= (ull)n * 1000003ULL + (ull)k * 998244353ULL;
    auto next64 = [&]() {
        state += 0x9E3779B97F4A7C15ULL;
        ull z = state;
        z = (z ^ (z >> 30)) * 0xBF58476D1CE4E5B9ULL;
        z = (z ^ (z >> 27)) * 0x94D049BB133111EBULL;
        return z ^ (z >> 31);
    };
    unsigned char sample[N*N+1];
    ll initial_total = 0, final_total = 0;
    F0(s, ACTUAL_SAMPLES) {
        for (int v = 0; v < n*n; v += 2) {
            ull bits = next64();
            sample[v] = (bits & 0xFFFFFFFFULL) < threshold[v];
            sample[v+1] = (bits >> 32) < threshold[v+1];
        }
        initial_total += SampleLoss(sample, initial_cut);
        final_total += SampleLoss(sample, final_cut);
    }
    ios::fmtflags flags = cerr.flags();
    streamsize prec = cerr.precision();
    cerr.setf(ios::fixed, ios::floatfield);
    cerr.precision(6);
    cerr << "Initial grid score (" << SAMPLES << " samples): " << initial_score << '\n';
    cerr << "Actual initial grid score (40000 samples): "
         << initial_total / (1.0 * ACTUAL_SAMPLES * n * n) << '\n';
    cerr << "Final grid score (" << SAMPLES << " samples): " << bscore << '\n';
    cerr << "Actual final grid score (40000 samples): "
         << final_total / (1.0 * ACTUAL_SAMPLES * n * n) << '\n';
    cerr.flags(flags);
    cerr.precision(prec);
}


void Prepare() {
    PR(n, k);
    sol.clear();
    bsol.clear();
    trees.clear();
    uncut.clear();
    F0(w, 10) uncut_bucket[w].clear();
    uncut_weight = 0;
    CL(-1, bucket_pos);
    CL(0, cut);
    CL(0, deg);
    CL(-1, uncut_pos);
    F0(i, n) F0(j, n) {
        int v = i*n+j;
        if (d[i][j]) trees.push_back({i, j});
        F0(t, 4) {
            int ni = i+di[t], nj = j+dj[t];
            if (ni >= 0 && ni < n && nj >= 0 && nj < n)
                adj[v][deg[v]++] = ni*n+nj;
        }
    }
    CL(0, dry_rows);
    F0(s, SAMPLES) F0(i, n) F0(j, n) {
        dry[s][i*n+j] = my.nextInt(10) < d[i][j];
        dry_rows[s][i] |= (unsigned long long)dry[s][i*n+j] << j;
    }
    bscore = inf;
    F0(i, LOGN) logs[i] = -log((i+0.5)/LOGN);
}

void UpdateBest() {
    if (score < bscore) {
        bscore = score;
        bsol = sol;
    }
}

int sa_consider[64], sa_accept[64], sa_regress[64], sa_total[64];


void Improve() {
    Rand sa_rng(1);
    vector<double> sa_type_prob = {0.4, 0.2, 0.6};
    int tn = 3;
    const int diag_i[4] = {-1, -1, 1, 1};
    const int diag_j[4] = {-1, 1, -1, 1};
    sa_rng.PrepareWeightedSample(sa_type_prob);
    F0(t, tn) {
        sa_consider[t] = sa_accept[t] = sa_regress[t] = sa_total[t] = 0;
        t_o[t] = 0;
    }


    int tot = 1, acc = 0;
    double T2 = 0.40, T1 = 0.00, TEMP = 0.0, r = 0.0;
    double startTime = Elapsed();
    double endTime = TL;
    if (sol.empty() || uncut.empty() || startTime >= endTime) return;
    for (int iter = 0; ; iter++) {
        double now = Elapsed();
        if (now >= endTime) { PR(iter); break; }
        r = (endTime - now) / (endTime - startTime);
        TEMP = T1 + (T2 - T1) * r;

        int tp = sa_rng.WeightedSample();
        AT(tp);
        sa_consider[tp]++;

        int p = my.nextInt(SZ(sol)), u;
        pii old = sol[p], next;
        if (tp == 0) {
            u = RandomUncut();
            next = uncut[u];
        } else {
            int t = my.nextInt(4);
            if (tp == 1) next = {old.first+di[t], old.second+dj[t]};
            else {
                if (SZ(sol) < 2) continue;
                // Keep the anchor and restore a different picked tree.
                int anchor = p;
                next = {sol[anchor].first+diag_i[t], sol[anchor].second+diag_j[t]};
                p = my.nextInt(SZ(sol)-1);
                if (p >= anchor) p++;
                old = sol[p];
            }
            if (next.first < 0 || next.first >= n || next.second < 0 || next.second >= n) continue;
            u = uncut_pos[next.first*n+next.second];
            if (u < 0) continue;
        }
        int a = old.first*n+old.second, b = next.first*n+next.second;
        cut[a] = false;
        cut[b] = true;
        double next_score = EvaluateSwap(a, b);
        double delta = next_score - score;

        sa_total[tp]++;
        if (delta > 0) tot++;
        if (delta <= 0 || delta <= TEMP * logs[my.nextInt(LOGN)]) {
            AcceptSwap(a, b);
            sa_accept[tp]++;
            if (delta > 0) { acc++; sa_regress[tp]++; }
            sol[p] = next;
            uncut[u] = old;
            uncut_pos[a] = u;
            uncut_pos[b] = -1;
            RemoveFromBucket(b);
            AddToBucket(a);
            score = next_score;
            UpdateBest();
        } else {
            cut[a] = true;
            cut[b] = false;
        }
    }
    if (1) {
        cerr << acc << "/" << tot << " "
             << 100.0 * acc / tot << " "
             << score << "/" << bscore << endl;
    }

    auto sa_rate = [](int num, int den) -> double {
        return den ? 100.0 * num / den : 0.0;
    };
    ios::fmtflags sa_flags = cerr.flags();
    streamsize sa_prec = cerr.precision();
    cerr.setf(ios::fixed, ios::floatfield);
    cerr.precision(1);
    cerr << "type      ms        consider  accept    regress   total     acc%      reg%\n";
    F0(ti, tn) {
        cerr.width(4); cerr << ti;
        cerr << "  ";
        cerr.width(9); cerr << 1000.0 * t_o[ti];
        cerr << "  ";
        cerr.width(8); cerr << sa_consider[ti];
        cerr << "  ";
        cerr.width(8); cerr << sa_accept[ti];
        cerr << "  ";
        cerr.width(8); cerr << sa_regress[ti];
        cerr << "  ";
        cerr.width(8); cerr << sa_total[ti];
        cerr << "  ";
        cerr.width(7); cerr << sa_rate(sa_accept[ti], sa_total[ti]);
        cerr << "  ";
        cerr.width(7); cerr << sa_rate(sa_regress[ti], sa_total[ti]);
        cerr << '\n';
    }
    cerr.flags(sa_flags);
    cerr.precision(sa_prec);
}

void SaSolution() {
    // Scale (d + 0.2 * sum(neighbor d)) by 10 for exact comparisons.
    F0(i, n) F0(j, n) {
        int v = i*n+j;
        W[i][j] = 10*d[i][j];
        F0(a, deg[v]) {
            int u = adj[v][a];
            W[i][j] += 2*d[u/n][u%n];
        }
    }
    F0(iter, k) {
        int best = -1, best_weight = 0;
        F0(t, SZ(trees)) {
            pii p = trees[t];
            int v = p.first*n+p.second;
            if (cut[v] || W[p.first][p.second] <= best_weight) continue;
            bool allowed = true;
            F0(a, deg[v]) if (cut[adj[v][a]]) allowed = false;
            if (allowed) {
                best = t;
                best_weight = W[p.first][p.second];
            }
        }
        if (best < 0) break;
        pii p = trees[best];
        sol.push_back(p);
        cut[p.first*n+p.second] = true;
    }
    F0(t, SZ(trees)) {
        pii p = trees[t];
        int v = p.first*n+p.second;
        if (cut[v]) continue;
        uncut_pos[v] = SZ(uncut);
        uncut.push_back(p);
        AddToBucket(v);
    }
    InitComponents();
    score = Evaluate();
    initial_score = score;
    initial_sol = sol;
    UpdateBest();
    Improve();
}

void Solve() {
    saveTime = GetSeconds();
    Prepare();
    
    SaSolution();

    cout << SZ(bsol) << endl;
    F0(i, SZ(bsol)) {
        cout << bsol[i].first << " " << bsol[i].second << endl;
    }

#ifdef LOCAL
    TraceScores();
#endif
    //Report();
}

void ReadInput() {
    cin >> n >> k;
    F0(i, n) {
        string row;
        cin >> row;
        F0(j, n) d[i][j] = row[j] - '0';
    }
}

int main(int argc, char* argv[]) {
    Init();

    int seed1 = 0, seed2 = 0;
    if (argc>1) {
        if (argc == 2) {
            seed1 = seed2 = atoi(argv[1]);
        } else {
            seed1 = atoi(argv[1]);
            seed2 = atoi(argv[2]);
        }
        STANDARD=0;
    }

    if (STANDARD) {
        ReadInput();
        Solve();
        return 0;
    }

    for (int seed=seed1; seed<=seed2; seed++) {
        if (seed>=0 && seed<10000) {
            char inp[128];
            sprintf(inp, "in/%04d.txt", seed);
            char outp[128];
            sprintf(outp, "out/%04d.txt", seed);
            ignore = freopen(inp, "r", stdin);
            ignore = freopen(outp, "w", stdout);
            ReadInput();
            Solve();
            cerr << "Seed #" << seed << " ";
            cerr << bscore << endl;
            //cout << "Score would be " << bscore << endl;
        } else {
            // Generate
            throw;
            Rand my(seed);
        }
    }

    return 0;
}