#include <bits/stdc++.h>
#include "supertrees.h"
#define v2d vector <vector <int> >
using namespace std;
constexpr int MAXN = 1e3 + 7;
int repl[MAXN];
int repl2[MAXN];
int repr[MAXN];
int rep[MAXN];
int type[MAXN];
void debug(int n)
{
for (int i = 0; i < n; i++)
{
cout << i << " " << rep[i] << " " << repl[i] << " " << repl2[i] << " " << repr[i] << " " << type[i] << "\n";
}
cout << "-----------------------------\n";
}
int Find(int a){
return rep[a] == a ? a : rep[a] = Find(rep[a]);
}
void Union(int a, int b, bool how){
if (how){
repl2[Find(b)] = min(repl2[Find(a)], min(repl2[Find(b)], max(repl[Find(b)], repl[Find(a)])));
repl[Find(b)] = min(repl[Find(a)], repl[Find(b)]);
repr[Find(b)] = max(repr[Find(b)], repr[Find(a)]);
rep[Find(a)] = Find(b);
}
rep[Find(a)] = Find(b);
}
int construct(v2d p)
{
int n = p.size();
v2d answer;
for (int i = 0; i < n; i++){
vector<int> cv;
for (int j = 0; j < n; j++)
cv.push_back(0);
answer.push_back(cv);
}
for (int i = 0; i < n; i++){
rep[i] = i;
repl[i] = i;
repl2[i] = MAXN;
repr[i] = i;
}
//debug(n);
for (int i = 0; i < n; i++){
for (int j = i + 1; j < n; j++)
{
if (p[i][j] == 1){
if (p[i] != p[j])
return 0;
if (Find(i) != Find(j)){
Union(i, j, false);
answer[i][j] = 1;
answer[j][i] = 1;
}
}
}
}
//debug(n);
for (int i = 0; i < n; i++){
if (i != Find(i))
continue;
for (int j = i + 1; j < n; j++)
{
if (j != Find(j))
continue;
if (p[i][j] == 2 || p[i][j] == 3)
{
if (type[i] == 0)
type[i] = p[i][j];
else if (type[i] != p[i][j])
return 0;
if (type[j] == 0)
type[j] = p[i][j];
else if (type[j] != p[i][j])
return 0;
for (int k = 0; k < n; k++)
{
if (p[i][k] == 0){
if (p[j][k] != 0)
return 0;
}
else if (p[i][k] == 1){
if (p[j][k] != p[i][j])
return 0;
}
else
if (p[j][k] != p[i][j] && p[j][k] != 1)
return 0;
}
if (Find(i) != Find(j)){
answer[repr[Find(i)]][repr[Find(j)]] = 1;
answer[repr[Find(j)]][repr[Find(i)]] = 1;
Union(i, j, true);
}
}
}
}
//debug(n);
for (int i = 0; i < n; i++){
if (type[Find(i)] != 0)
{
if (repr[Find(i)] == repl[Find(i)])
return 0;
answer[repr[Find(i)]][repl[Find(i)]] = 1;
answer[repl[Find(i)]][repr[Find(i)]] = 1;
if (type[Find(i)] == 3)
{
if (repl2[Find(i)] >= repr[Find(i)])
return 0;
answer[repl2[Find(i)]][repr[Find(i)]] = 1;
answer[repr[Find(i)]][repl2[Find(i)]] = 1;
}
type[Find(i)] = 0;
}
}
//debug(n);
build(answer);
return 1;
}
