#include <bits/stdc++.h>
#include "supertrees.h"
using namespace std;
const int MAXN = 1e3 + 10;
int marc[MAXN], group[MAXN];
int p[MAXN][MAXN];
vector<vector<int>> b;
void add(int u, int v){
b[u][v] = b[v][u] = 1;
}
bool solve(vector<int> &cur){
int n = (int) cur.size();
// sei que ta todo mundo na mesma comp
vector<int> cycle;
for(int i=0; i<n; i++){
for(int j=i; j<n; j++){
if(p[cur[i]][cur[j]] == 2){
cycle = {cur[i], cur[j]};
}
}
}
if(cycle.empty()){
// entao todo mundo eh 1
for(int i=1; i<n; i++) add(cur[i - 1], cur[i]);
for(auto x : cur){
for(auto y : cur){
if(p[x][y] != 1){
return false;
}
}
}
return true;
}
for(int i=0; i<n; i++){
if(cur[i] == cycle[0] || cur[i] == cycle[1]) continue;
bool ok = true;
for(auto x : cycle){
if(p[cur[i]][x] != 2){
ok = false;
}
}
if(ok) cycle.push_back(cur[i]);
}
if((int) cycle.size() < 3) return false;
for(int i=1; i<cycle.size(); i++) add(cycle[i - 1], cycle[i]);
add(cycle.back(), cycle[0]);
for(auto x : cycle){
group[x] = x;
for(int i=0; i<n; i++){
if(p[cur[i]][x] == 1 && x != cur[i]){
group[cur[i]] = x;
add(cur[i], x);
}
}
}
return true;
}
int construct(vector<vector<int>> p_){
int n = (int) p_.size();
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
p[i][j] = p_[i][j];
if(p[i][j] == 3) return 0;
}
}
for(int i=0; i<n; i++){
b.push_back({});
for(int j=0; j<n; j++) b.back().push_back(0);
}
int comp = 0;
for(int i=0; i<n; i++){
if(!marc[i]){
vector<int> cur;
for(int j=0; j<n; j++){
if(!marc[j] && p[i][j] > 0){
cur.push_back(j);
}
}
comp ++;
for(auto j : cur) marc[j] = comp;
if(!solve(cur)) return 0;
}
}
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
if(p[i][j] > 0 && marc[i] != marc[j]){
return 0;
}
}
}
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
if(p[i][j] == 1){
if(group[i] != group[j]) return 0;
} else if(p[i][j] == 2){
if(group[i] == group[j]) return 0;
}
}
}
build(b);
return 1;
}
