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
#include<bits/stdc++.h>
    using namespace std;
    const int inf = 1000000000;
    vector<int> dijkstra (int start, vector<vector<pair<int, int>>>&graf){
        int ile_wierzch = graf.size();
        vector<int> odl(ile_wierzch, inf);
        odl[start]=0;

        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> kolejka;
        kolejka.push(make_pair(0, start));
        while(!kolejka.empty()){
            int wierzch = kolejka.top().second;
            int koszt = kolejka.top().first;
            kolejka.pop();
            if(koszt<=odl[wierzch]){
                for(pair<int, int> krawedz : graf[wierzch]){
                    int sasiad = krawedz.first, kasa = krawedz.second;
                    if(odl[wierzch]+kasa<odl[sasiad]){
                        odl[sasiad]=odl[wierzch]+kasa;
                        kolejka.push(make_pair(odl[sasiad], sasiad));
                    }
                }
            }
        }
        return odl;
    }
    int main(){
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        int ilepyt;
        cin>>ilepyt;
        for(int i=0; i<ilepyt; i++){
            // -----------------------------------------PIERWSZA DJKIKSTRA-------------------------
            int ile_wierzch;
            cin>>ile_wierzch;
            vector<vector<pair<int, int>>> graf(ile_wierzch);

            for(int j=0; j<ile_wierzch; j++){
                string pol;
                cin>>pol;
                for(int k = 0; k<ile_wierzch; k++){
                    if(pol[k]=='1'){
                        graf[j].push_back(make_pair(k, 1));
                        graf[k].push_back(make_pair(j, 1));
                    }
                }
            }
            int start = 0;
            vector<int> min_odl = dijkstra(start, graf);

            // ----------------------------------KONIEC---------------------------------------

            //--------------------------SZUKAJ SREDNICY GRAFU-------------------------------
            int maxj=0;
            int cotomaxj=0;
            for(int j=0; j<min_odl.size(); j++){
                if(min_odl[j]>maxj){
                    cotomaxj=j;
                    maxj=min_odl[j];
                }
            }
            min_odl=dijkstra(cotomaxj, graf);
            maxj=0;
            int starecotomaxj=cotomaxj;
            cotomaxj=0;
            for(int j=0; j<min_odl.size(); j++){
                if(min_odl[j]>maxj){
                    cotomaxj=j;
                    maxj=min_odl[j];
                }
            }
            //-----------------------KONIEC-----------------------------------
            // ----------------USTAW 2 NAJDALEJ OD SIBIE JAKO 0--------------
            bool zn=false;
            for (auto& krawedz : graf[cotomaxj]) {
                if (krawedz.first == starecotomaxj) {
                    krawedz.second = 0;
                    zn=true;
                    break;
                }
            }
            for (auto& krawedz : graf[starecotomaxj]) {
                if (krawedz.first == cotomaxj) {
                    krawedz.second = 0;
                    zn=true;
                    break;
                }
            }
            if(zn==false){
                graf[cotomaxj].push_back(make_pair(starecotomaxj, 0));
                graf[starecotomaxj].push_back(make_pair(cotomaxj, 0));
            }
            // -----------------KONIEC-------------------------------------
            //-----------------------ZNAJDZ SREDNICE I WYPISZ------------------------
            min_odl=dijkstra(0, graf);
            maxj=0;
            cotomaxj=0;
            for(int j=0; j<min_odl.size(); j++){
                if(min_odl[j]>maxj){
                    cotomaxj=j;
                    maxj=min_odl[j];
                }
            }

            min_odl=dijkstra(cotomaxj, graf);
            maxj=0;
            cotomaxj=0;
            for(int j=0; j<min_odl.size(); j++){
                if(min_odl[j]>maxj){
                    cotomaxj=j;
                    maxj=min_odl[j];
                }
            }
            cout<<maxj<<"\n";
            //-------------KONIEC KONIEC KONIEC JUPIIIIIIIIIIIII!-------------

    }
    return 0;

    }