#include "supertrees.h"
#include <bits/stdc++.h>
#define forn(i, a, b) for(int i = int(a); i <= int(b); ++ i)
using namespace std;
const int lim = 1e3;
int graph[lim + 2][lim + 2];
bool visitado[lim + 2];
int componente[lim + 2];
vector<int> lineas[lim + 2];
int n, numcomp;
void dfs(int u){
forn(v, 0, n - 1){
if(v != u && graph[u][v] && !componente[v]){
componente[v] = componente[u];
dfs(v);
}
}
}
int construct(vector<vector<int>> p) {
n = p.size();
forn(i, 0, n - 1){
forn(j, 0, n - 1){
graph[i][j] = p[i][j];
if(graph[i][j] == 3){
return 0;
}
}
}
forn(i, 0, n - 1){
if(!componente[i]){
componente[i] = ++ numcomp;
dfs(i);
}
}
forn(i, 0, n - 1){
forn(j, i + 1, n - 1){
if(!graph[i][j] && componente[i] == componente[j]){
return 0;
}
}
}
vector<int> aux[lim + 2];
forn(i, 0, n - 1){
if(!visitado[i]){
lineas[componente[i]].push_back(i);
visitado[i] = 1;
forn(j, 0, n - 1){
if(graph[i][j] == 1){
aux[i].push_back(j);
}
}
for(int &u : aux[i]){
visitado[u] = 1;
forn(j, 0, n - 1){
if(graph[u][j] == 1 && graph[i][j] != 1){
return 0;
}
}
}
}
}
forn(i, 1, numcomp){
if((int) lineas[i].size() == 2){
return 0;
}
}
vector<vector<int>> res;
res.resize(n);
forn(i, 0, n - 1){
res[i].resize(n);
forn(j, 0, n - 1){
res[i][j] = 0;
}
}
int tamanio;
forn(i, 1, numcomp){
tamanio = lineas[i].size();
forn(j, 1, tamanio - 1){
res[lineas[i][j - 1]][lineas[i][j]] = 1;
res[lineas[i][j]][lineas[i][j - 1]] = 1;
}
if(tamanio > 1){
res[lineas[i][0]][lineas[i][tamanio - 1]] = 1;
res[lineas[i][tamanio - 1]][lineas[i][0]] = 1;
}
for(int &u : lineas[i]){
tamanio = aux[u].size();
forn(j, 1, tamanio - 1){
res[aux[u][j]][aux[u][j - 1]] = 1;
res[aux[u][j - 1]][aux[u][j]] = 1;
}
}
}
build(res);
return 1;
}
