#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
const int NAX = 1002;
vector<int> parent(NAX, -1);
vector<vector<int> > P(NAX, vector<int>(NAX));
vector<vector<int> > answer;
vector<set<int> > adj(NAX);
int n;
int Find(int u){
if (parent[u] == -1) return u;
return parent[u] = Find(parent[u]);
}
int sub12(){
for (int i=0; i<n; i++){
for (int j=0; j<n; j++){
if (i==j) continue;
int x = Find(i), y = Find(j);
if (P[i][j] == 1){
if (x!=y) return 0;
}else{
if (x==y) return 0;
}
}
}
build(answer);
return 1;
}
int sub3(){
for (int i=0; i<n; i++){
for (int j=0; j<n; j++){
if (i==j) continue;
int x = Find(i), y = Find(j);
if (x == y){
adj[x].insert(i);
adj[x].insert(j);
}
}
}
for (int i=0; i<n; i++){
if (adj[i].size() > 1)
for (auto j=adj[i].begin(); j!=adj[i].end(); j++){
auto nextnode = j;
nextnode++;
if (nextnode == adj[i].end()) nextnode = adj[i].begin();
answer[*j][*nextnode] = answer[*nextnode][*j] = 1;
}
}
for (int i=0; i<n; i++){
for (int j=0; j<n; j++){
if (i==j) continue;
int x = Find(i), y = Find(j);
if (P[i][j] == 0){
if (x==y) return 0;
}else{
if (x!=y) return 0;
}
}
}
build(answer);
return 1;
}
int construct(vector<vector<int> > p) {
n = p.size();
for (int i=0; i<n; i++){
vector<int> row(n);
answer.push_back(row);
}
int twos = 0;
for (int i=0; i<n; i++){
for (int j=0; j<n; j++){
if (p[i][j] == 2) twos++;
P[i][j] = p[i][j];
}
}
for (int i=0; i<n; i++){
for (int j=0; j<n; j++){
if (i==j) continue;
if (P[i][j] > 0){
int x = Find(i), y = Find(j);
if (x!=y){
parent[x]=y;
if (twos == 0) answer[i][j]=answer[j][i]=1;
}
}
}
}
if (twos) return sub3();
else return sub12();
}
