#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;
}
} else if(P[i][j] == 3) 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));
}
vector<vector<int>> twos(N);
for(int i = 0; i < N; ++i) {
for(int j = 0; j < N; ++j) {
if(P[i][j] == 2) {
twos[i].push_back(j);
}
}
}
ans = vector<vector<int>>(N, vector<int>(N, 0));
map<vector<int>, vector<int>> cycles;
for(auto& u : comps) {
for(int i = 0; i < (int)D[u].size(); ++i) {
if(D[u][i] == u) swap(D[u][i], D[u][0]);
}
for(int i = 1; i < (int)D[u].size(); ++i) {
if(twos[u] != twos[D[u][i]]) return 0;
ans[u][D[u][i]] = 1;
ans[D[u][i]][u] = 1;
}
twos[u].push_back(u);
{
set<int> s;
for(auto& v : twos[u]) {
s.insert(parent(v));
}
twos[u] = vector<int>(begin(s), end(s));
}
cycles[twos[u]].emplace_back(u);
}
for(auto& u : cycles) {
if(u.first != u.second) return 0;
if(u.first.size() == 2) return 0;
if(u.first.size() == 1) continue;
ans[u.first[0]][u.first.back()] = 1;
ans[u.first.back()][u.first[0]] = 1;
for(int i = 1; i < (int)u.first.size(); ++i) {
ans[u.first[i]][u.first[i - 1]] = 1;
ans[u.first[i - 1]][u.first[i]] = 1;
}
}
build(ans);
return 1;
}
