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
def solve():
    import sys
    from collections import deque
    import numpy as np

    data = sys.stdin.read().split()
    if not data:
        return
    t = int(data[0])
    idx = 1
    output_lines = []
    for _ in range(t):
        n = int(data[idx])
        idx += 1
        # Wczytanie opisu grafu – macierzy sąsiedztwa
        graph = []
        for i in range(n):
            s = data[idx]
            idx += 1
            # Reprezentacja w postaci listy wartości bool (True gdy '1', False gdy '0')
            row = [ch == '1' for ch in s]
            graph.append(row)
        
        # Obliczenie macierzy odległości przy pomocy BFS
        dist = [[-1] * n for _ in range(n)]
        for start in range(n):
            dq = deque([start])
            dist[start][start] = 0
            while dq:
                u = dq.popleft()
                d_u = dist[start][u]
                # Przeglądamy wszystkich potencjalnych sąsiadów
                for v in range(n):
                    if graph[u][v] and dist[start][v] == -1:
                        dist[start][v] = d_u + 1
                        dq.append(v)
        
        # Wyznaczamy oryginalną średnicę grafu
        L = 0
        for i in range(n):
            for j in range(n):
                if dist[i][j] > L:
                    L = dist[i][j]
        
        # Konwersja macierzy odległości do numpy.array dla operacji wektorowych
        d = np.array(dist)
        
        # Szukamy optymalnego teleportu – dla każdej pary (x, y)
        best_candidate = L
        for x in range(n):
            for y in range(x + 1, n):
                # Dla każdej pary teleportu obliczamy:
                # candidate_R = max_{u in V} min{d(u,x), d(u,y)}
                candidate_R = int(np.max(np.minimum(d[:, x], d[:, y])))
                candidate_val = 2 * candidate_R  # po użyciu teleportu droga nie przekroczy 2*candidate_R
                if candidate_val < best_candidate:
                    best_candidate = candidate_val
        
        # Ostateczna odpowiedź to minimum pomiędzy L (bez teleportu)
        # a najlepszym wynikiem po dodaniu teleportu.
        ans = min(L, best_candidate)
        output_lines.append(str(ans))
    
    sys.stdout.write("\n".join(output_lines))


if __name__ == '__main__':
    solve()