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
121
122
123
124
125
126
127
128
129
130
131
132
133
#include <algorithm>
#include <fstream>
#include <iostream>
#include <numeric>
#include <random>
#include <sstream>
#include <string>
#include <deque>
#include <vector>

using graf_t = std::vector< std::vector< int >>;

struct Zadanie {
	int n;
	graf_t siatka;
	std::vector< int > rozm;
	int src = 0;
	int dst = 0;
};

struct Najdalszy {
	int pkt;
	int odl;
};

std::istream& operator>> (std::istream& is, Zadanie& zad) {
	is >> zad.n;

	zad.siatka.resize(zad.n);
	zad.rozm.resize(zad.n);

	for (int i = 0; i < zad.n; ++i) {
		std::string maska; is >> maska;

		for (int j = 0; j < maska.size(); ++j) {
			if (maska[j] == '1') zad.siatka[i].push_back(j);
		}

		zad.rozm[i] = zad.siatka[i].size();
	}

	return is;
}

std::ostream& operator<< (std::ostream& os, Najdalszy& n) {
	os << "{" << n.pkt << "," << n.odl << "}";
	return os;
}

int teleportuj(int n, Zadanie const& zad) {
	return n == zad.src ? zad.dst : n;
}

Najdalszy idz_daleko(Zadanie const& zad, int start) {
	start = teleportuj(start, zad);

	std::vector< int > odleglosci(zad.n, -1);
	std::deque< int > kolejka = {start};

	odleglosci[start] = 0;
	Najdalszy wynik{start, 0};

	while (! kolejka.empty()) {
		int wezel = kolejka.back();
		kolejka.pop_back();

		for (int sasiad: zad.siatka[wezel]) {
			sasiad = teleportuj(sasiad, zad);

			if (-1 < odleglosci[sasiad]) continue;

			odleglosci[sasiad] = odleglosci[wezel] + 1;
			kolejka.push_front(sasiad);

			if (wynik.odl < odleglosci[sasiad]) {
				wynik = {sasiad, odleglosci[sasiad]};
			}
		}
	}

	return wynik;
}

int szacuj_srednice(Zadanie const& zad) {
	Najdalszy start = idz_daleko(zad, 0);
	Najdalszy koniec = idz_daleko(zad, start.pkt);
	
	return koniec.odl;
}

int licz_srednice(Zadanie const& zad) {
	int wynik = 0;

	int l_prob = std::max(3,  std::min(zad.n / 10, 10));

	for (int i = 0; i < l_prob; ++i) {
		Najdalszy start = idz_daleko(zad, i);
		Najdalszy koniec = idz_daleko(zad, start.pkt);
		wynik = std::max(wynik, koniec.odl);
	}

	return wynik;
}

int rozwiaz(Zadanie& zad) {
	int wynik = zad.n - 1;

	for (int i = 0; i < zad.n - 1; ++i) {
		for (int j = i + 1; j < zad.n; ++j) {
			zad.src = i;
			zad.dst = j;		
			std::copy(zad.siatka[i].begin(), zad.siatka[i].end(), std::back_inserter(zad.siatka[j]));

			wynik = std::min(wynik, licz_srednice(zad));

			zad.siatka[j].resize(zad.rozm[j]);
			zad.src = 0;
			zad.dst = 0;
		}
	}

	return wynik;
}

int main() {
	std::istream& WEJ = std::cin;

	int n_testow; WEJ >> n_testow;
	for (int i = 0; i < n_testow; ++i) {
		Zadanie zad; WEJ >> zad;
		std::cout << rozwiaz(zad) << "\n";
	}
}