#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
int n,res=0;
vector<vector<int>>v,pref,pref1;
vector<vector<bool>>g;
void izracuni()
{
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
pref[i][j+1]=pref[i][j]+v[i][j];
pref1[i+1][j]=pref1[i][j]+v[i][j];
}
}
}
int najdi(int l1,int r1,int l2,int r2)
{
if(r1==r2)return pref1[max(l1,l2)+1][r1]-pref1[min(l1,l2)][r1];
else return pref[l1][max(r1,r2)+1]-pref[l1][min(r1,r2)];
}
void proveri(int x1,int x2)
{
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
if(v[i][j]==0)
{
if(najdi(x1,x2,x1,j)+najdi(x1,j,i,j)==0||najdi(x1,x2,i,x2)+najdi(i,x2,i,j)==0)
{
g[n*i+j][n*x1+x2]=true;
g[n*x1+x2][n*i+j]=true;
}
}
}
}
}
void lettry(vector<int>v1,vector<int>v2)
{
if(v1.size()+v2.size()<=res)return;
if(v2.empty())
{
res=max(res,int(v1.size()));return;
}
for(int i=0;i<v2.size();i++)
{
vector<int>vn1=v1,vn2;
vn1.push_back(v2[i]);
for(int j=i+1;j<v2.size();j++)if(g[v2[i]][v2[j]])vn2.push_back(v2[j]);
lettry(vn1,vn2);
}
}
int biggest_stadium(int N,vector<vector<int>> G)
{
n=N;
v=G;
pref.resize(n+1,vector<int>(n+1));
pref1.resize(n+1,vector<int>(n+1));
g.resize(n*n,vector<bool>(n*n));
vector<int>temp,temp1;
izracuni();
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
if(v[i][j]==0)
{
proveri(i,j);
temp.push_back(n*i+j);
}
}
}
lettry(temp1,temp);
return res;
}
