#include <bits/stdc++.h>
#include "supertrees.h"
// #define int long long
// #define fi first
// #define se second
//
// #define sz(a) (int)((a).size())
// #define all(a) (a).begin(), (a).end()
//
// #define lsb(x) (x & (-x))
// #define vi vector<int>
// #define YES { cout << "YES" << endl; return; }
// #define NO { cout << "NO" << endl; return; }
//
// using ll = long long;
// using pii = std::pair<int, int>;
const int NMAX = 1e5;
using namespace std;
struct DSU {
vector<int> data;
DSU(int N) : data(N, -1) {}
int find(int k) { return data[k] < 0 ? k : data[k] = find(data[k]); }
int unite(int x, int y) {
if ((x = find(x)) == (y = find(y))) return false;
if (data[x] > data[y]) swap(x, y);
data[x] += data[y];
data[y] = x;
return true;
}
template<typename F>
int unite(int x, int y,const F &f) {
if ((x = find(x)) == (y = find(y))) return false;
if (data[x] > data[y]) swap(x, y);
data[x] += data[y];
data[y] = x;
f(x, y);
return true;
}
int size(int k) { return -data[find(k)]; }
int same(int x, int y) { return find(x) == find(y); }
};
vector<int>L[NMAX + 5];
int construct(vector<vector<int>> D) {
int n = D.size();
vector<vector<int>>sol(n, vector<int>(n, 0));
unique_ptr<DSU[]> ds(new DSU[3]{DSU(n), DSU(n), DSU(n)});
for (int i = 0; i < n; ++i) {
for (int j = 0; j < i; ++j) {
if (D[i][j] == 3)
return 0;
ds[D[i][j]].unite(i, j);
}
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < i; ++j) {
if ((ds[1].same(i, j) && D[i][j] != 1) || (ds[2].same(i, j) && D[i][j] != 2))
return 0;
}
}
for (int i = 0; i < n; ++i) {
if (ds[1].find(i) == i)
L[ds[2].find(i)].push_back(i);
else {
sol[i][ds[1].find(i)] = 1;
sol[ds[1].find(i)][i] = 1;
}
}
for (int i = 0; i < n; ++i) {
if (L[i].size() < 2) continue;
if (L[i].size() == 2) return 0;
///prima data il fac lant
for (int j = 1; j < L[i].size(); ++j) {
int cur = L[i][j];
int prev = L[i][j - 1];
sol[cur][prev] = 1;
sol[prev][cur] = 1;
}
///conectez ultimul element din lant cu primul ca sa se formeze ciclu
int first = L[i][0];
int last = L[i][L[i].size() - 1];
sol[first][last] = 1;
sol[last][first] = 1;
}
build(sol);
return 1;
}
// signed main() {
// cin.tie(nullptr)->sync_with_stdio(false);
//
// return 0;
// }
