#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int col[1010];
bool visited[1010];
int construct(vector<vector<int>> p) {
int n = p.size();
vector<vector<int>> answer, C;
answer.resize(n);
for (int i=0;i<n;i++) answer[i].resize(n, 0);
bool valid0 = 1;
for (int i=0;i<n;i++){
for (int j=0;j<n;j++) if (p[i][j]==3) valid0 = 0;
}
if (!valid0) return 0;
for (int i=0;i<n;i++) if (!visited[i]){
visited[i] = 1;
vector<int> tmp;
C.push_back(tmp);
C.back().push_back(i);
col[i] = C.size();
for (int j=0;j<n;j++) if (!visited[j] && p[i][j]){
C.back().push_back(j);
col[j] = C.size();
visited[j] = 1;
}
}
bool valid1 = 1;
for (int i=0;i<n;i++){
for (int j=0;j<n;j++){
if (i==j) valid1 &= (p[i][j]==1);
else if (col[i]==col[j]) valid1 &= (p[i][j]>0);
else valid1 &= (p[i][j]==0);
}
}
if (!valid1) return 0;
for (auto &V:C){
vector<vector<int>> C1;
vector<int> col1(1010, 0);
fill(visited, visited+1010, 0);
for (auto &x:V) if (!visited[x]){
visited[x] = 1;
vector<int> tmp;
C1.push_back(tmp);
C1.back().push_back(x);
col1[x] = C1.size();
for (int j=0;j<n;j++) if (col[j]==col[x] && !visited[j] && p[x][j]==1){
C1.back().push_back(j);
visited[j] = 1;
col1[j] = C1.size();
}
}
bool valid2 = 1;
for (auto &x:V){
for (auto &y:V){
if (col1[x]==col1[y]) valid2 &= (p[x][y]==1);
else valid2 &= (p[x][y]==2);
}
}
if (!valid2) return 0;
if ((int)C1.size()==2) return 0;
for (int i=0;i<(int)C1.size()-1;i++){
answer[C1[i][0]][C1[i+1][0]] = 1;
answer[C1[i+1][0]][C1[i][0]] = 1;
}
if ((int)C1.size()>1){
answer[C1.back()[0]][C1[0][0]] = 1;
answer[C1[0][0]][C1.back()[0]] = 1;
}
for (auto &U:C1){
for (int i=1;i<(int)U.size();i++){
answer[U[0]][U[i]] = 1;
answer[U[i]][U[0]] = 1;
}
}
}
build(answer);
return 1;
}
