#include"supertrees.h"
#include<bits/stdc++.h>
using namespace std;
int N;
vector<vector<int>> P, ans, D;
vector<int> par;
int parent(int x) {
return (par[x] == x ? x : par[x] = parent(par[x]));
}
int unite(int x, int y) {
x = parent(x);
y = parent(y);
if(x == y) return 1;
if((int)D[x].size() < (int)D[y].size()) swap(x, y);
for(auto& u : D[x]) for(auto& v : D[y]) {
if(P[u][v] != 1) return 0;
}
for(auto& u : D[y]) D[x].emplace_back(u);
par[y] = x;
return 1;
}
int construct(vector<vector<int>> _p) {
swap(P, _p);
N = (int)P.size();
D.resize(N);
par.resize(N); iota(begin(par), end(par), 0);
for(int i = 0; i < N; ++i) D[i].push_back(i);
for(int i = 0; i < N; ++i) {
for(int j = i + 1; j < N; ++j) {
if(P[i][j] == 1) {
if(!unite(i, j)) {
return 0;
}
}
}
}
vector<int> comps;
{
set<int> s;
for(int i = 0; i < N; ++i) {
s.insert(parent(i));
}
comps = vector<int>(begin(s), end(s));
}
ans = vector<vector<int>>(N, vector<int>(N, 0));
for(auto& u : comps) {
if(D[u].size() == 1) continue;
for(int i = 1; i < (int)D[u].size(); ++i) {
ans[D[u][i]][D[u][i - 1]] = 1;
ans[D[u][i - 1]][D[u][i]] = 1;
}
}
vector<bool> did(N);
for(int i = 0; i < N; ++i) {
if(did[i]) continue;
vector<int> ids = {i};
for(int j = i + 1; j < N; ++j) {
if(P[i][j] == 2) {
did[j] = 1;
ids.push_back(j);
}
}
if((int)ids.size() <= 1) continue;
{
set<int> s;
for(auto& u : ids) {
s.insert(parent(u));
}
ids = vector<int>(begin(s), end(s));
}
ans[ids[0]][ids.back()] = 1;
ans[ids.back()][ids[0]] = 1;
for(int i = 1; i < (int)ids.size(); ++i) {
ans[ids[i]][ids[i - 1]] = 1;
ans[ids[i - 1]][ids[i]] = 1;
}
}
build(ans);
return 1;
}
