#include "supertrees.h"
#include <bits/stdc++.h>
#define FOR(i, j, k, l) for(int i = (j); i < (k); i += (l))
#define FORD(i, j, k, l) for(int i = (j);i >= (k); i -= (l))
#define REP(i, n) FOR(i, 0, n, 1)
#define REPD(i, n) FORD(i, n, 0, 1)
#define pb push_back
typedef long long ll;
using namespace std;
struct dsu{
vector<int> p;
int n;
dsu(int _n){
p.resize(n, -1);
}
int find(int x){
return (p[x] < 0 ? x : p[x] = find(p[x]));
}
bool sameSet(int u, int v){
return (find(u) == find(v));
}
bool join(int a, int b){
a = find(a); b = find(b);
if(a == b)
return false;
if(p[a] > p[b])
swap(a, b);
p[a] += p[b];
p[b] = a;
return true;
}
};
int construct(vector<vector<int>> p) {
int n = p.size();
REP(i, n){
REP(j, n){
if(p[i][j] == 3)
return 0;
}
}
vector<vector<int>> answer(n, vector<int>(n, 0));
dsu d(n);
dsu d2(n); // with 2s. if multiple 1 repres are in same comp, then create cycle from them;
REP(i, n){
REP(j, i){
if(p[i][j] == 1){
d.join(i, j);
d2.join(i, j);
}
}
}
REP(i, n){
if(d.find(i) != i){
int rp = d.find(i);
answer[rp][i] = answer[i][rp] = 1;
}
}
REP(i, n){
REP(j, i){
if(p[i][j] == 2)
d2.join(i, j);
}
}
vector<vector<int>> buckets(n);
REP(i, n){
if(d.find(i) == i){
buckets[d2.find(i)].pb(i);
}
}
// can't be 2 in p[i][j] = 2;
REP(i, n){
if(buckets[i].size() == 2)
return 0;
if(buckets[i].size() > 2){
REP(j, buckets[i].size()){
int u = buckets[i][j];
int v = buckets[i][(j + 1) % buckets[i].size()];
answer[u][v] = answer[v][u] = 1;
}
}
}
// now some connectivity checks;
// d2 is final connectivity; d are 1 components
// if p[i][j] == 0; they cant be connected in any way
// if p[i][j] == 2, they can't be connected in d;
REP(i, n){
REP(j, i){
if(p[i][j] == 0 && d2.sameSet(i, j))
return 0;
if(p[i][j] == 2 && d.sameSet(i, j))
return 0;
}
}
build(answer);
return 1;
}
