#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 1e3 + 1;
int N;
int P[NMAX][NMAX];
int head[NMAX];
bool Edge[NMAX][NMAX];
vector < int > G[NMAX];
class DisjointSets
{
int T[NMAX], Size[NMAX];
private:
inline int Find (int X)
{
if(X == T[X])
return X;
return (T[X] = Find(T[X]));
}
inline void my_swap (int &x, int &y)
{
x = (x ^ y), y = (x ^ y), x = (x ^ y);
return;
}
public:
inline void Initialize (int N)
{
for(int i = 1; i <= N; ++i)
T[i] = i, Size[i] = 1;
return;
}
inline bool Unify (int X, int Y)
{
X = Find(X), Y = Find(Y);
if(X == Y)
return 0;
if(Size[X] < Size[Y])
my_swap(X, Y);
Size[X] += Size[Y], Size[Y] = 0;
T[Y] = X;
return 1;
}
inline int Who_is_the_boss (int Node)
{
return Find(Node);
}
} DSU;
vector < int > List[NMAX];
void Build_type_1 ()
{
DSU.Initialize(N);
for(int i = 1; i <= N; ++i)
for(int j = 1; j <= N; ++j)
if(P[i][j] == 1)
DSU.Unify(i, j);
for(int i = 1; i <= N; ++i)
head[i] = DSU.Who_is_the_boss(i), List[head[i]].push_back(i);
return;
}
int construct (vector < vector < int > > p)
{
N = (int)p.size();
for(int i = 0; i < N; ++i)
for(int j = 0; j < N; ++j)
{
P[i + 1][j + 1] = p[i][j];
if(p[i][j] == 3)
return 0;
}
Build_type_1();
for(int i = 1; i <= N; ++i)
if(!List[i].empty())
{
for(int j = 0; j < (int)List[i].size() - 1; ++j)
Edge[List[i][j]][List[i][j + 1]] = Edge[List[i][j + 1]][List[i][j]] = 1;
}
for(int i = 1; i <= N; ++i)
for(int j = 1; j <= N; ++j)
if(P[i][j] == 0)
if(head[i] == head[j])
return 0;
vector < vector < int > > ans;
for(int i = 0; i < N; ++i)
{
vector < int > _temp;
for(int j = 0; j < N; ++j)
if(Edge[i + 1][j + 1])
_temp.push_back(1);
else
_temp.push_back(0);
ans.push_back(_temp);
}
build(ans);
return 1;
}
