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
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;

constexpr int N = 400;
vector<int> graf[N+9];
int dst[N+9][N+9];

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int t,n;
    string a;
    cin >> t;
    while(t--){
        cin >> n;
        for (int x=1;x<=n;x++){
            cin >> a;
            for (int y=0;y<n;y++){
                if (a[y]=='1')graf[x].push_back(y+1);
            }
        }
        for (int pocz=1;pocz<=n;pocz++){
            for (int x=1;x<=n;x++)dst[pocz][x]=1e9;
            dst[pocz][pocz]=0;
            vector<int> kolej;
            kolej.push_back(pocz);
            for (int x=0;x<kolej.size();x++){
                int v=kolej[x];
                for (int y:graf[v]){
                    if (dst[pocz][y]==1e9){
                        dst[pocz][y]=dst[pocz][v]+1;
                        kolej.push_back(y);
                    }
                }
            }
        }
        int best=1e9;
        for (int x1=1;x1<=n;x1++){
            for (int x2=1;x2<=n;x2++){
                int temp=0;
                for (int x=1;x<=n;x++){
                    for (int y=1;y<=n;y++){
                        temp=max(temp, min(dst[x][y],min(dst[x][x1]+dst[x2][y]+1,dst[x][x2]+dst[x1][y]+1)));
                    }
                }
                best=min(best,temp);
            }
        }
        cout << best << '\n';
    }
}