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
/**
 * Patryk Kisielewski
 * 
 * Potyczki Algorytmiczne 2025
 * Zadanie: TEL - Teleport [A]
*/
#include <iostream>
#include <queue>
#include <vector>

using namespace std;

pair<int,int> longestDistance(const std::vector<std::vector<int>>& graph, int v1, int t1, int t2) {
    int v, dist;
    std::vector<int> distances(graph.size(), -1);
    distances[v1] = 0;
    queue<int> q;
    q.push(v1);
    while (!q.empty()) {
        v = q.front();
        q.pop();
        dist = distances[v];
        if (v == t1 || v == t2) {
            distances[t1] = dist;
            distances[t2] = dist;
            for (auto& next : graph[t1]) {
                if (distances[next] != -1) continue;
                distances[next] = dist + 1;
                q.push(next);
            }
            for (auto& next : graph[t2]) {
                if (distances[next] != -1) continue;
                distances[next] = dist + 1;
                q.push(next);
            }
            continue;
        }
        for (auto& next : graph[v]) {
            if (distances[next] != -1) continue;
            distances[next] = dist + 1;
            q.push(next);
        }
    }
    return {v, dist};
}

int main() {
    int t, n;
    char c;
    cin >> t;

    for (int ti = 0; ti < t; ++ti) {
        cin >> n;

        std::vector<std::vector<int>> graph(n, std::vector<int>());

        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                cin >> c;
                if (c == '1') {
                    graph[i].push_back(j);
                }
            }
        }

        int res = n + 1;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                res = min(res, longestDistance(graph, longestDistance(graph, 0, i, j).first, i, j).second);
            }
        }
        cout << res << endl;
    }

    return 0;
}