#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define lsb(x) (x&(-x))
#define pii pair<int,int>
#define ss second
#define ff first
#define piii pair<int,pii>
#define debu(x) (cerr << #x << " = "<< x << "\n")
#define debu2(x,y) (cerr << #x << " = "<< x << " " << #y << " = " << y << "\n")
#define debu3(x,y,z) (cerr << #x << " = "<< x << " " << #y << " = " << y << " " << #z << " = " << z<< "\n")
#define bitout(x,y) {\
cerr << #x << " : ";\
for (int justforbits = y; justforbits >=0; justforbits--)cout << (((1 << justforbits) & x)>=1);\
cout << "\n";\
}
#define rangeout(j,rangestart,rangeend) {\
cerr << "outputting " << #j<< ":\n";\
for (int forrang = rangestart; forrang <= rangeend; forrang++)cerr << j[forrang] << " ";\
cerr<<"\n";\
}
#define c1 {cerr << "Checkpoint 1! \n\n";cerr.flush();}
#define c2 {cerr << "Checkpoint 2! \n\n";cerr.flush();}
#define c3 {cerr << "Checkpoint 3! \n\n";cerr.flush();}
#define c4 {cerr << "Checkpoint 4! \n\n";cerr.flush();}
#define vi vector<int>
#define vpii vector<pii>
#define fr(i,x,y) for(int i=x;i<=y;i++)
vector<vector<int>>ans;
void makeline(vi& x)
{
//c1;
for(int i=1;i<x.size();i++)
{
ans[x[i]][x[i-1]]=true;
ans[x[i-1]][x[i]]=true;
}
//c2;
}
void makecycle(vi& x)
{
for(int i=1;i<x.size();i++)
{
ans[x[i]][x[i-1]]=true;
ans[x[i-1]][x[i]]=true;
}
if(x.size()>2)
{
ans[x[0]][x.back()]=true;
ans[x.back()][x[0]]=true;
}
}
int construct(std::vector<std::vector<int>> p)
{
int t1,t2,t3,t4;
int n=p.size();//c1;
ans.resize(n,vi(n,false));
vector<vector<int>>sets;//c2;
for(int i=0;i<n;i++)
{
if(p[i][i]!=1)return 0;//c4;
for(int ii=0;ii<n;ii++)if(p[i][ii]==3||p[i][ii]!=p[ii][i])return 0;
t1=0;//c3;
for(int ii=0;ii<sets.size();ii++)
{
bool troo=false;
for(int xx:sets[ii])
{
if(p[i][xx]){troo=true;}
}
t1+=troo;
if(troo)sets[ii].pb(i);
}//c2;
if(t1==0)
{
vi t5;t5.pb(i);
sets.pb(t5);
}
if(t1>1)return 0;
}//c3;
for(int i=0;i<sets.size();i++)
{
for(int xx:sets[i]){for(int yy:sets[i])if(!p[xx][yy])return 0;}
vector<vi>trees;
for(int k:sets[i])
{
t1=0;
for(int ii=0;ii<trees.size();ii++)
{
bool troo=false;
for(int xx:trees[ii])
{
if(p[k][xx]==1){troo=true;}
}
t1+=troo;
if(troo)trees[ii].pb(k);
}
if(t1==0){vi t5;t5.pb(k);trees.pb(t5);}
if(t1>1){return 0;}
}
vi t5;
for(int ii=0;ii<trees.size();ii++)
{
for(int xx:trees[ii]){for(int yy:trees[ii])if(p[xx][yy]!=1)return 0;}
makeline(trees[ii]);t5.pb(trees[ii][0]);
}
if(t5.size()==2)return 0;
makecycle(t5);
}
build(ans);
return 1;
}
