#include "supertrees.h"
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define all(v) v.begin(), v.end()
using namespace std;
int n;
vector <vector <int>> res;
struct DSU{
int n;
vector <int> par;
void init(int n1) {
n = n1;
par.assign(n+1, -1);
}
int get(int u) {
if (par[u] < 0) return u;
return par[u] = get(par[u]);
}
bool un(int a, int b) {
a = get(a);
b = get(b);
if(a == b) return 0;
if (par[a] < par[b]) swap(a, b);
par[b] += par[a];
par[a] = b;
return 1;
}
};
int construct(vector<vector<int>> p) {
n = p.size();
res.assign(n, vector <int>(n, 0));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (p[i][j] == 3) return 0;
if (p[i][j] != p[j][i]) return 0;
}
}
vector <pair<vector <int>, vector <int>>> g(n);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (!p[i][j] || i == j) continue;
if (p[i][j] == 1) g[i].ff.pb(j);
else g[i].ss.pb(j);
}
}
DSU dsu;
dsu.init(n);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (p[i][j]) dsu.un(i, j);
}
}
vector <vector <int>> cmp;
vector <int> is(n, -1);
for (int i = 0; i < n; i++) {
int c = dsu.get(i);
if (is[c] == -1) {
is[c] = cmp.size();
cmp.pb({});
}
is[i] = is[c];
}
for (int i = 0; i < n; i++) cmp[is[i]].pb(i);
// cerr << "Components built:\n";
// // for (auto &i : cmp) { for (int &j : i) cerr << j << ' '; cerr << endl; }
// cerr << endl;
vector <int> col(n, 0);
for (auto &i : cmp) {
vector <vector <int>> ch;
for (int &j : i) {
if (col[j]) continue;
ch.pb({j});
col[j] = 1;
// cerr << "Childs of " << j << ": ";
for (int &z : g[j].ff) {
// cerr << z << ' ';
if (col[z]) return 0;
ch.back().pb(z), col[z] = 1;
}
// cerr << endl;
}
// cerr << "\nAll chains in [ ";
// for (int &j : i) cerr << j << ' ';
// cerr << "] built:\n";
// // for (auto &j : ch) for (int &z : j) cerr << z << ' '; cerr << endl;
// cerr << endl;
for (auto &j : ch) {
for (int z = 1; z < j.size(); z++) {
if (res[j[z]][j[z-1]] || res[j[z-1]][j[z]]) return 0;
res[j[z]][j[z-1]] = 1, res[j[z-1]][j[z]] = 1;
}
}
if (ch.size() == 1) continue;
for (int j = 0; j < ch.size(); j++) {
int z = (j + 1) % ch.size();
int a = ch[j][0], b = ch[z][0];
if (res[a][b] || res[b][a]) return 0;
res[a][b] = 1;
res[b][a] = 1;
}
}
// cerr << "\n\nResult vector:\n";
// // for (auto &i : res) { for (int &j : i) cerr << j; cerr << endl; }
build(res);
return 1;
}
/*
1 1
1 1
*/
