#include<bits/stdc++.h>
#include"supertrees.h"
using namespace std;
typedef long long ll;
struct dsu{
vector<int> parent, size;
int N;
void assign(int dsusize){
N = dsusize;
parent.assign(N, 0);
iota(parent.begin(), parent.end(), 0);
size.assign(N, 1);
}
int find(int v){
return parent[v] = (parent[v] == v ? v : find(parent[v]));
}
void merge(int v, int u){
if(find(v) == find(u))
return;
if(size[find(v)] < size[find(u)])
swap(u, v);
size[find(v)]+= size[find(u)];
parent[find(u)] = parent[find(v)];
}
bool is_same(int v, int u){
return (find(v) == find(u));
}
};
dsu DSU;
vector<vector<int>> ans;
void make_edge(int x, int y){
ans[x][y] = ans[y][x] = 1;
}
int construct(vector<vector<int>> p){
int n = p.size();
ans.assign(n, vector<int>(n));
DSU.assign(n);
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(p[i][j] != p[j][i])
return 0;
if(p[i][j])
DSU.merge(i, j);
}
if(p[i][i] != 1)
return 0;
}
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(DSU.is_same(i, j) != (p[i][j] != 0))
return 0;
}
}
vector<vector<int>> groups(n);
for(int i = 0; i < n; i++)
groups[DSU.find(i)].push_back(i);
for(vector<int>& G : groups){
if(G.size() <= 1)
continue;
vector<int> mid, other;
mid.reserve(n);
other.reserve(n);
for(int x : G){
bool alltwo = true;
for(int y : G)
alltwo&= (x == y || p[x][y] == 2);
if(alltwo)
mid.push_back(x);
else
other.push_back(x);
}
vector<int> color(n, -1);
vector<vector<int>> side(2);
if(other.size())
color[other[0]] = 0;
for(int x : other){
for(int y : other){
if(x == y)
continue;
if(p[x][y] == 1){
if(color[y] != -1 && color[y] != color[x])
return 0;
color[y] = color[x];
}
else if(p[x][y] == 2){
if(color[y] != -1 && color[y] == color[x])
return 0;
color[y] = 1-color[x];
}
}
assert(color[x] != -1);
side[color[x]].push_back(x);
}
if(side[0].size())
mid.push_back(side[0][0]);
if(side[1].size())
mid.push_back(side[1][0]);
if(mid.size() == 2)
return 0;
if(mid.size() > 1)
for(int i = 0; i < (int) (mid.size()); i++)
make_edge(mid[i], mid[(i+1)%((int) (mid.size()))]);
for(int i = 1; i < (int) (side[0].size()); i++)
make_edge(side[0][i], side[0][i-1]);
for(int i = 1; i < (int) (side[1].size()); i++)
make_edge(side[1][i], side[1][i-1]);
}
build(ans);
return 1;
}
