#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
int construct(vector<vector<int>> p) {
int n = p.size();
vector<vector<int>> adj(n, vector<int>(n));
vector<int> pai(n), comp[n];
iota( pai.begin(), pai.end(), 0 );
for( int i = 0; i < n; i++ ) comp[i].push_back(i);
function<int(int)> find = [&]( int a ){ return (( a == pai[a]) ? a : pai[a] = find(pai[a]) ); };
auto join = [&]( int a, int b ){
a = find(a); b = find(b);
if( a == b ) return 1;
pai[b] = a;
adj[a][b] = 1;
adj[b][a] = 1;
int ok = 1;
for( int i : comp[a] ) for( int j : comp[b] ) if( p[i][j] != 1 ) ok = 0;
for( int i : comp[b] ) comp[a].push_back(i);
return ok;
};
for( int i = 0; i < n; i++ ) for( int j = i + 1; j < n; j++ ) if( (p[i][j] == 1 && !join( i, j )) || p[i][j] == 3 ) return 0;
vector<int> marc(n);
for( int i = 0; i < n; i++ ) if( pai[i] == i && !marc[i] ){
queue<int> fila; fila.push(i);
vector<int> ciclo;
marc[i] = true;
while( !fila.empty() ){
int cur = fila.front(); fila.pop();
ciclo.push_back(cur);
for( int j = 0; j < n; j++ ) if( pai[j] == j && !marc[j] && p[cur][j] == 2 ) fila.push(j), marc[j] = true;
}
if( ciclo.size() < 2 ) continue;
if( ciclo.size() == 2 ) return 0;
for( int j = 0; j < ciclo.size(); j++ ) for( int k = j + 1; k < ciclo.size(); k++ )
for( int a : comp[ciclo[j]] ) for( int b : comp[ciclo[k]] ) if( p[a][b] != 2 ) return 0;
for( int i = 0; i + 1 < ciclo.size(); i++ ) adj[ciclo[i]][ciclo[i + 1]] = adj[ciclo[i + 1]][ciclo[i]] = 1;
adj[i][ciclo.back()] = adj[ciclo.back()][i] = 1;
}
build(adj);
return 1;
}
