#include "supertrees.h"
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct DSU {
vector<int> v;
void init (int n) {v.assign(n, -1);}
int get(int x) {return v[x] < 0 ? x : v[x] = get(v[x]);}
void unite(int x, int y) {
x = get(x); y = get(y);
if (x == y) return;
if (v[x] > v[y]) swap(x, y);
v[x] += v[y]; v[y] = x;
}
bool same (int x, int y) {return (get(x) == get(y));}
};
int construct(vector<vector<int> > p) {
int n=p.size();
DSU all; all.init(n);
DSU one; one.init(n);
vector<vector<int> > ans(n, vector<int>(n, 0));
for (int i = 0; i < n; i++) {
for (int j = i+1; j < n; j++) {
if (p[i][j] == 3) return 0;
if (p[i][j] != 0) all.unite(i, j);
if (p[i][j] == 1 && !one.same(i, j)) {
one.unite(i, j);
ans[i][j] = 1;
ans[j][i] = 1;
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (p[i][j] == 0 && all.same(i, j)) {
//cout << i << " " << j << endl;
return 0;
}
if (p[i][j] == 2 && one.same(i, j)) return 0;
if (p[i][j] != 0 && !all.same(i, j)) return 0;
}
}
for (int leader = 0; leader < n; leader++) {
vector<int> v;
for (int i = 0; i < n; i++) {
if (one.get(i) == i && all.get(i) == leader) v.push_back(i);
}
if ((int)v.size() > 1) {
if ((int)v.size()==2) return 0;
int m = (int)v.size();
for (int i = 0; i < m; i++) {
int j = v[(i+1)%m];
ans[v[i]][j] = 1;
ans[j][v[i]] = 1;
}
}
}
build(ans);
return 1;
}
