#include "supertrees.h"
#include <vector>
using namespace std;
const int NMAX = 1e3 + 1;
int N, roads[NMAX][NMAX];
bool G[NMAX][NMAX];
vector < int > roots;
vector < int > list[NMAX];
vector < vector < int > > ans;
class DSU
{
static const int NMAX = 1e3 + 1;
int T[NMAX], Size[NMAX];
private:
inline int Find (int Node)
{
if(Node == T[Node])
return Node;
return (T[Node] = Find(T[Node]));
}
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);
T[Y] = X;
Size[X] += Size[Y], Size[Y] = 0;
return 1;
}
inline int Id (int Node)
{
return Find(Node);
}
inline int Sz (int Id)
{
return Size[Id];
}
} trees, cycles;
static inline void Add_Edge (int X, int Y)
{
G[X][Y] = G[Y][X] = 1;
return;
}
static inline void Build_Trees ()
{
trees.Initialize(N);
for(int i = 1; i < N; ++i)
for(int j = (i + 1); j <= N; ++j)
if(roads[i][j] == 1)
trees.Unify(i, j);
for(int i = 1; i <= N; ++i)
{
int father = trees.Id(i);
if(father == i)
roots.push_back(i);
else
Add_Edge(i, father);
}
return;
}
static inline void Build_Cycles ()
{
cycles.Initialize(N);
for(int i = 0; i < (int)roots.size() - 1; ++i)
for(int j = (i + 1); j < (int)roots.size(); ++j)
{
int X = roots[i], Y = roots[j];
if(roads[X][Y] == 2)
cycles.Unify(X, Y);
}
for(auto it : roots)
{
int father = cycles.Id(it), i = it;
if(cycles.Sz(father) > 1)
list[father].push_back(i);
}
return;
}
static inline void Go_to_collect_solution ()
{
for(int i = 1; i <= N; ++i)
{
vector < int > line;
for(int j = 1; j <= N; ++j)
line.push_back(G[i][j]);
ans.push_back(line);
}
return;
}
int construct (vector < vector < int > > p)
{
N = (int)p.size();
for(int i = 1; i <= N; ++i)
for(int j = 1; j <= N; ++j)
{
roads[i][j] = p[i - 1][j - 1];
if(roads[i][j] > 2)
return 0;
}
Build_Trees();
for(int i = 1; i < N; ++i)
for(int j = (i + 1); j <= N; ++j)
if(roads[i][j] == 0 && trees.Id(i) == trees.Id(j))
return 0;
Build_Cycles();
for(int i = 1; i <= N; ++i)
{
if(list[i].empty())
continue;
if((int)list[i].size() == 1 || (int)list[i].size() == 2)
return 0;
for(int p1 = 0; p1 < (int)list[i].size() - 1; ++p1)
for(int p2 = (p1 + 1); p2 < (int)list[i].size(); ++p2)
if(roads[list[i][p1]][list[i][p2]] != 2)
return 0;
for(int p1 = 0; p1 < (int)list[i].size() - 1; ++p1)
Add_Edge(list[i][p1], list[i][p1 + 1]);
Add_Edge(list[i][0], list[i].back());
}
Go_to_collect_solution(), build(ans);
return 1;
}
