#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
struct DSU {
vector<int> s, p;
DSU(int sz) : s(sz + 1, 1), p(sz + 1, -1) {}
int find(int x) {
return (p[x] == -1) ? x : (p[x] = find(p[x]));
}
bool join(int x, int y) {
x = find(x);
y = find(y);
if(x == y) return false;
if(s[x] < s[y]) swap(x, y);
s[x] += s[y]; p[y] = x;
return true;
}
};
int construct(vector<vector<int>> p) {
int n = p.size();
vector<vector<int>> answer;
for (int i = 0; i < n; i++) {
vector<int> row;
row.resize(n);
answer.push_back(row);
}
DSU loli(n);
auto add = [&](int x, int y) {
x = loli.find(x);
y = loli.find(y);
if(x == y) return;
answer[x][y] = 1;
answer[y][x] = 1;
loli.join(x, y);
};
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
if(p[i][j] == 1) {
add(i, j);
}
if (p[i][j] == 3) return 0;
}
}
vector<int> keep;
vector<bool> vis(n);
function<void(int)> dfs = [&](int x) {
vis[x] = true;
keep.push_back(x);
for(int i = 0; i < n; i++) {
int y = loli.find(i);
if(p[x][y] && !vis[y]) dfs(y);
}
};
for(int i = 0; i < n; i++) {
int x = loli.find(i);
if(!vis[x]) {
keep.clear(); dfs(x);
if(keep.size() == 1) continue;
if(keep.size() == 2) return 0;
for(int j = 1; j < (int)keep.size(); j++) {
answer[keep[j]][keep[j - 1]] = 1;
answer[keep[j - 1]][keep[j]] = 1;
}
answer[keep[0]][keep.back()] = 1;
answer[keep.back()][keep[0]] = 1;
for(int x : keep) {
for(int y : keep) {
if(x == y) continue;
if(p[x][y] != 2) return 0;
}
}
}
}
vector<vector<int>> T(n);
for(int i = 0; i < n; i++) {
T[loli.find(i)].push_back(i);
}
for(int i = 0; i < n; i++) {
for(int x : T[i]) {
for(int y : T[i]) {
if(p[x][y] != 1) return 0;
}
}
}
/*for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
cout << answer[i][j] << " \n"[j == n - 1];
}
}*/
build(answer);
return 1;
}
