#include <bits/stdc++.h>

using namespace std;

const int N = 2005; const long long INF = 0x3f3f3f3f3f3f3f3fLL;
int n, d[N][N];

int pre[N], low[N], sccno[N], dfs_clock;
stack<int> stk; int scc_c;
inline void Tarjan(int u) {
    pre[u] = low[u] = ++dfs_clock; stk.push(u);
    for(int v = 1; v <= n; v ++) if(d[u][v]) {
        if(!pre[v]) {
            Tarjan(v); low[u] = min(low[u], low[v]);
        } else if(!sccno[v]) low[u] = min(low[u], pre[v]);
    }
    if(low[u] >= pre[u]) {
        int y; scc_c ++;
        do {
            y = stk.top(); stk.pop(); sccno[y] = scc_c;
        } while(y != u);
    }
}

struct edge {
    int from, to, dist;
    edge(int u = 0, int v = 0, int d = 0) : from(u), to(v), dist(d) {}
};
vector<edge> G[N];
int ind[N], outd[N];
inline pair<int, int> Build() {
    for(int i = 1; i <= n; i ++)
    for(int j = 1; j <= n; j ++) 
        if(d[i][j] && sccno[i] != sccno[j]) {
            //G[sccno[i]].emplace_back(edge(i, j, d[i][j]));
            G[sccno[j]].emplace_back(edge(j, i, d[i][j]));
            ind[sccno[j]] ++, outd[sccno[i]] ++;
        }
    pair<int, int> ans = {-1, -1};
    for(int i = 1; i <= scc_c; i ++) {
        if(!ind[i]) ans.first = i;
        if(!outd[i]) ans.second = i;
    }
    if(ans.first == -1 || ans.second == -1) assert(false);
    return ans;
}

typedef pair<long long, int> pli;
pair<int, int> prv[N]; long long dist[N]; bool vis[N];
inline void Dijkstra(int S) {
    priority_queue<pli, vector<pli>, greater<pli>> Q;
    dist[S] = 0; Q.push({dist[S], S});
    while(!Q.empty()) {
        int u = Q.top().second; Q.pop(); if(vis[u]) continue;
        vis[u] = true;
        for(auto &e : G[u]) { int v = sccno[e.to];
            if(dist[v] > dist[u] + e.dist) {
                dist[v] = dist[u] + e.dist; prv[v] = {e.from, e.to};
                Q.push({dist[v], v});
            }
        }
    }
}

inline void Init() {
    memset(pre + 1, 0, sizeof(int) * n);
    memset(low + 1, 0, sizeof(int) * n);
    memset(sccno + 1, 0, sizeof(int) * n);
    memset(ind + 1, 0, sizeof(int) * n), memset(outd + 1, 0, sizeof(int) * n);
    memset(dist + 1, 0x3f, sizeof(long long) * n);
    memset(vis + 1, 0, sizeof(bool) * n);
    for(int i = 1; i <= n; i ++) G[i].clear();
    dfs_clock = scc_c = 0;
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0);

    int T; cin >> T;
    while(T --) {
        cin >> n; Init();
        for(int i = 1; i <= n; i ++)
            for(int j = 1; j <= n; j ++)
                cin >> d[i][j];
        if(n == 2) {cout << "NO\n"; continue; }
        cout << "YES\n";
        for(int i = 1; i <= n; i ++) 
            if(!pre[i]) Tarjan(i);
        if(scc_c == 1) {cout << "0 0\n"; continue; }
        pair<int, int> P = Build(); Dijkstra(P.second);
        
        vector<pair<int, int>> ans;
        int u = P.first;
        while(u != P.second) {
            ans.emplace_back(prv[u]);
            u = sccno[prv[u].first];
        }
        cout << ans.size() << ' ' << dist[P.first] << '\n';
        for(auto &pr : ans)
            cout << pr.second << ' ' << pr.first << '\n';
    }


    return 0;
}