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
#include <bits/stdc++.h>
using namespace std;
void solve()
{
	int n;
	cin>>n;
	vector<vector<int>>g(n);
	for(int i=0; i<n; i++)
	{
		string s;
		cin>>s;
		for(int j=0; j<n; j++)
			if(s[j]=='1')
				g[i].push_back(j);
	}
	vector<vector<int>>bfs(n,vector<int>(n));
	vector<int>q(n);
	/*for(int i=0; i<n; i++)
	{
		cout<<i<<".    ";
		for(auto j:g[i])
			cout<<j<<" ";
		cout<<"\n";
	}*/
	for(int i=0; i<n; i++)
	{
		bfs[i][i]=1;
		int p1=0;
		int p2=1;
		q[0]=i;
		while(p2<n)
		{
			int a=q[p1++];
			for(int j=0; j<g[a].size(); j++)
				if(bfs[i][g[a][j]]==0)
				{
					bfs[i][g[a][j]]=bfs[i][a]+1;
					q[p2++]=g[a][j];
				}
		}
	}
	for(int i=0; i<n; i++)
		for(int j=0; j<n; j++)
			bfs[i][j]--;
	vector<pair<int,pair<int,int>>>sus;
	for(int i=0; i<n; i++)
		for(int j=i+1; j<n; j++)
			sus.push_back({bfs[i][j],{i,j}});
	sort(sus.begin(),sus.end());
	int dupa=sus[sus.size()-1].first;
	vector<pair<int,int>>huell;
	for(int i=0; i<n; i++)
		for(int j=i+1; j<n; j++)
			huell.push_back({i,j});
	random_shuffle(huell.begin(),huell.end());
	for(auto sus1:huell)
	{
		int i=sus1.first;
		int j=sus1.second;
		int lokalny_kurwidolek=0;
		for(int k=sus.size()-1; k>=0; k--)
		{
			int o1=min(bfs[i][sus[k].second.first],bfs[j][sus[k].second.first]);
			int o2=min(bfs[i][sus[k].second.second],bfs[j][sus[k].second.second]);
			//cout<<i<<" "<<j<<" "<<o1<<" "<<sus[k].second.first<<" "<<o2<<" "<<sus[k].second.second<<" "<<lokalny_kurwidolek<<"chujujujuj\n";
			if(o1+o2>=sus[k].first)
				lokalny_kurwidolek=max(lokalny_kurwidolek,sus[k].first);
			else
				lokalny_kurwidolek=max(lokalny_kurwidolek,o1+o2);
			if(lokalny_kurwidolek>=sus[k].first||lokalny_kurwidolek>=dupa){
				break;}
		}
		dupa=min(dupa,lokalny_kurwidolek);
	}
	cout<<dupa<<"\n";
}
int main()
{
	ios_base::sync_with_stdio(NULL);
	cin.tie(NULL);
	cout.tie(NULL);
	int t;
	cin>>t;
	while(t--)
		solve();
}