#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) {}
void init() {
iota(p.begin(), p.end(), 0);
}
int find(int x) {
return (p[x] == x) ? 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);
loli.init();
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);
}
}
}
vector<int> keep;
vector<bool> vis(n);
vector<vector<int>> T(n);
for(int i = 0; i < n; i++) {
T[loli.find(i)].push_back(i);
}
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) {
int a = keep[0];
int b = keep[1];
if(T[a].size() == 1 && T[b].size() == 1) return 0;
if(T[a].size() > T[b].size()) swap(a, b);
answer[T[a][0]][T[b][0]] = 1;
answer[T[b][0]][T[a][0]] = 1;
answer[T[a][0]][T[b][1]] = 1;
answer[T[b][1]][T[a][0]] = 1;
}
else {
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 i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
if(p[i][j] == 0) continue;
if(loli.find(i) == loli.find(j)) {
if(p[i][j] != 1) return 0;
} else {
if(p[i][j] != 2) 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;
}
