#include<bits/stdc++.h>

using namespace std;
const int inf = 1e9 + 1;
const int MOD = 1e9 + 7;

/*
const int N = 1e5 + 5;
int fac[N], inv[N];

int sum(int a, int b) { return (a + b + MOD + MOD) % MOD; }
int mul(int a, int b) { return 1ll * a * b % MOD; }
int Pow(int a, int b) {
    int res = 1;
    for (; b; b>>=1, a = mul(a, a)) if (b&1) {
        res = mul(res, a);
    }
    return res;
}
int C(int n, int k) {
    return mul(fac[n], mul(inv[k], inv[n - k]));
}
void prep() {
    fac[0] = 1;
    for (int i = 1; i < N; i++) fac[i] = mul(fac[i - 1], i);
    inv[N - 1] = Pow(fac[N - 1], MOD - 2);
    for (int i = N - 2; i >= 0; i--) inv[i] = mul(inv[i + 1], i + 1);
}
*/
const int N = 2e3 + 3;
int d[N][N];
bool mark[N];
int comp[N];
int dis[N], par[N];
int n; 
vector<int> vi;

void dfs(int v, int p = 0) {
    mark[v] = 1;
    for (int i = 1; i <= n; i++) if (i != p) {
        if (d[v][i] && !mark[i]) {
            dfs(i, v);
        }
    }
    vi.push_back(v);
}
void dfs_comp(int v, int c, int p = 0) {
    comp[v] = c;
    for (int i = 1; i <= n; i++) if (v != p) {
        if (d[i][v] && !comp[i]) {
            dfs_comp(i, c, v);
        }
    }
}
void Solve() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            scanf("%d", &d[i][j]);
        }
    }
    if (n == 1) {
        printf("YES\n0 0\n");
        return;
    }
    if (n == 2) {
        printf("NO\n");
        return;
    }
    fill(mark, mark + n + 1, 0);
    vi.clear();
    for (int i = 1; i <= n; i++) {
        if (!mark[i])
            dfs(i);
    }
    reverse(vi.begin(), vi.end());
    int c = 0;
    fill(comp, comp + n + 1, 0);
    for (int i = 0; i < vi.size(); i++) {
        if (!comp[vi[i]]) dfs_comp(vi[i], ++c);
    }
    fill(dis, dis + n + 1, inf);
    fill(par, par + n + 1, 0);
    for (int i = 1; i <= n; i++) {
        if (comp[i] == c) {
            dis[i] = 0;
            par[i] = 0;
        }
    }
    fill(mark, mark + n + 1, 0);
    for (int i = 1; i <= n; i++) {
        int v = 0;
        for (int u = 1; u <= n; u++) {
            if (mark[u]) continue;
            if (v) {
                if (dis[u] < dis[v]) v = u;
            } else v = u;
        }
        if (v == -1) break;
        mark[v] = 1;
        for (int i = 1; i <= n; i++) {
            if (dis[i] > dis[v] + d[i][v]) {
                dis[i] = dis[v] + d[i][v];
                par[i] = v;
            }
        }
    }
    int ans = inf;
    int dest = 0;
    for (int i = 1; i <= n; i++) if (comp[i] == 1) {
        if (dis[i] < ans) {
            ans = dis[i];
            dest = i;
        }
    }
    printf("YES\n");
    vector< pair<int, int> > vec;
    while (comp[dest] != c) {
        int p = par[dest];
        if (d[dest][p]) {
            vec.push_back({dest, p});
        }
        dest = p;
    }
    printf("%d %d\n", vec.size(), ans);
    for (auto [u, v] : vec) {
        printf("%d %d\n", u, v);
    }
}

int main() {
    // prep();
    // cout << C(5, 4) << endl;
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1; scanf("%d", &t);
    while (t--) {
        Solve();
    }
}