1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#include <bits/stdc++.h>

using std::cin, std::cout;
using i32 = int;
using u32 = unsigned int;
using i64 = long long;
using u64 = unsigned long long;
const char endl = '\n';

const int MAX_N = 405;
const int INF = INT_MAX / 4;

int dist[MAX_N][MAX_N]; // [from][to]
bool conn[MAX_N][MAX_N];

struct edge {
    int a, b;
};

void solve() {
    int n; cin >> n;
    std::vector<edge> edges;

    std::string s;
    for (int a = 0; a < n; a++) {
        cin >> s;
        for (int b = 0; b < n; b++) {
            conn[a][b] = s[b] == '1';
            if (a < b) edges.emplace_back(a, b);
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i == j) dist[i][j] = 0;
            else if (conn[i][j]) dist[i][j] = 1;
            else dist[i][j] = INF;
        }
    }

    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dist[i][j] = std::min(dist[i][j], dist[i][k] + dist[j][k]);
            }
        }
    }

    int lp1, lp2;
    int lp = 0;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (dist[i][j] > lp) {
                lp = dist[i][j];
                lp1 = i;
                lp2 = j;
            }
        }
    }

    int prev[MAX_N];
    bool visited[MAX_N]{};
    std::queue<int> next;
    next.emplace(lp1);

    while (not next.empty()) {
        int curr = next.front();
        next.pop();

        for (int i = 0; i < n; i++) {
            if (visited[i]) continue;
            if (conn[curr][i]) {
                next.emplace(i);
                visited[i] = true;
                prev[i] = curr;
            }
        }
    }

    std::vector<int> path;
    int v = lp2;
    while (v != lp1) {
        path.emplace_back(v);
        v = prev[v];
    }
    path.emplace_back(lp1);
    

    int min = INT_MAX;

    for (int t1 : path) {
        for (int t2 : path) {
            if (t1 > t2) continue;

            int max = 0;

            for (int i = 0; i < n; i++) {
                for (int j = 0; j < i; j++) {
                    int d = std::min({dist[i][j], dist[i][t1] + dist[t2][j], dist[i][t2] + dist[t1][j]});
                    if (d > max) max = d;
                }
            }

            if (max < min) min = max;
        }
    }

    cout << min << endl;
}

int main() {
    std::ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);

    int t;
    cin >> t;
    for (int i = 0; i < t; i++) solve();

    return 0;
}