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
#include <iostream>
#include <vector>
#include <queue>
#include <tuple>

using namespace std;

// poczatek koniec i dlugosc
tuple<int, int, int> najdluzsza_sciezka(vector<vector<int>> &graf, bool jest_tep, int tep1, int tep2)
{
    int n = graf.size();
    int poczatek = -1;
    int koniec = -1;
    int maksymalna_sciezka = 0;
    for (int s = 0; s < n; s++)
    {
        queue<int> kolejka;
        vector<int> odleglosci(n, -1);
        odleglosci[s] = 0;
        kolejka.push(s);
        while (!kolejka.empty())
        {
            int v = kolejka.front();
            kolejka.pop();
            for (int w : graf[v])
            {
                if (odleglosci[w] == -1)
                {
                    kolejka.push(w);
                    if (jest_tep && ((v == tep1 && w == tep2) || (v == tep2 && w == tep1)))
                    {
                        odleglosci[w] = odleglosci[v];
                    }
                    else
                    {
                        odleglosci[w] = odleglosci[v] + 1;
                    }
                    if (odleglosci[w] > maksymalna_sciezka)
                    {
                        maksymalna_sciezka = odleglosci[w];
                        poczatek = s;
                        koniec = w;
                    }
                }
            }
        }
    }
    tuple<int, int, int> rezultat = {poczatek, koniec, maksymalna_sciezka};
    return rezultat;
}

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

    int t, n;
    cin >> t;
    char polaczenie;
    for (int test = 0; test < t; test++)
    {
        cin >> n;
        vector<vector<int>> graf;
        graf.reserve(n);
        for (int i = 0; i < n; i++)
        {
            vector<int> sasiedzi_wierzcholka;
            for (int j = 0; j < n; j++)
            {
                cin >> polaczenie;
                if (polaczenie == '1')
                    sasiedzi_wierzcholka.push_back(j);
            }
            graf.push_back(sasiedzi_wierzcholka);
        }
        tuple<int, int, int> pierwszy_etap = najdluzsza_sciezka(graf, false, -1, -1);
        graf[get<0>(pierwszy_etap)].push_back(get<1>(pierwszy_etap));
        graf[get<1>(pierwszy_etap)].push_back(get<0>(pierwszy_etap));
        tuple<int, int, int> drugi_etap = najdluzsza_sciezka(graf, true, get<0>(pierwszy_etap), get<1>(pierwszy_etap));
        cout << get<2>(drugi_etap) << "\n";
    }
}