#include "supertrees.h"
#include<bits/stdc++.h>
using namespace std;
int n;
vector<vector<int> > adj;
vector<int> parent;
vector<bool> visited;
vector<int> e;
bool works = true;
vector<vector<int> > p;
int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); }
bool same_set(int a, int b) { return get(a) == get(b); }
int size(int x) { return -e[get(x)]; }
bool unite(int x, int y){
x = get(x), y = get(y);
if (x == y) return false;
if (e[x] > e[y]) swap(x, y);
e[x] += e[y]; e[y] = x;
return true;
}
void dfs(int u){
visited[u] = true;
for(int v = 0; v < n; v++){
if(same_set(u, v) && p[u][v] == 0){
works = false;
return;
}
if(p[u][v] == 0){
continue;
}
if(p[u][v] != 0 && same_set(u, v)){
continue;
}
parent[v] = u;
unite(u, v);
dfs(v);
if(!works){
return;
}
}
}
void dfs2(int u){
visited[u] = true;
for(int v = 0; v < n; v++){
if(u == v) continue;
if(same_set(u, v) && p[u][v] == 0){
works = false;
return;
}
if(p[u][v] == 0){
continue;
}
if(p[u][v] != 0 && same_set(u, v)){
continue;
}
parent[v] = u;
unite(u, v);
dfs2(v);
if(!works){
return;
}
}
}
int construct(vector<vector<int> > p_){
n = p_.size();
p.resize(n, vector<int>(n));
p = p_;
bool has2 = false;
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(p[i][j] == 2){
has2 = true;
}
}
}
adj.resize(n);
visited.resize(n, false);
parent.resize(n, -1);
e.resize(n, -1);
if(!has2){
for(int i = 0; i < n; i++){
if(!visited[i]){
dfs(i);
}
}
if(works){
vector<vector<int> > answer(n, vector<int>(n, 0));
for(int i = 0; i < n; i++){
if(parent[i] == -1) continue;
answer[i][parent[i]] = 1;
answer[parent[i]][i] = 1;
}
build(answer);
return 1;
}
else{
return 0;
}
}
else{
for(int i = 0; i < n; i++){
if(!visited[i]){
dfs2(i);
}
}
if(works){
vector<vector<int> > answer(n, vector<int>(n, 0));
vector<vector<int> > comps(n);
for(int i = 0; i < n; i++){
comps[get(i)].push_back(i);
}
for(int i = 0; i < n; i++){
if(comps[i].empty()){
continue;
}
int m = comps[i].size();
if(m == 1){
continue;
}
if(m == 2){
return 0;
}
for(int j = 0; j < m; j++){
int x = comps[i][j];
int y = comps[i][(j + 1) % m];
answer[x][y] = 1;
answer[y][x] = 1;
}
}
build(answer);
return 1;
}
else{
return 0;
}
}
}
