#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(same_set(u, v) && p[u][v] == 0){
works = false;
return;
}
if(p[u][v] == 0){
continue;
}
if(p[u][v] != 0 && visited[v] && !same_set(u, v)){
works = false;
return;
}
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> > stuff(n);
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(same_set(i, j)){
stuff[get(i)].push_back(j);
}
}
}
vector<vector<int> > answer(n, vector<int>(n, 0));
for(int i = 0; i < n; i++){
if(stuff[i].empty()) continue;
for(int j = 0; j < (int)stuff[i].size() - 1; j++){
answer[stuff[i][j]][stuff[i][j + 1]] = 1;
answer[stuff[i][j + 1]][stuff[i][j]] = 1;
}
answer[stuff[i].back()][stuff[i][0]] = 1;
answer[stuff[i][0]][stuff[i].back()] = 1;
}
build(answer);
return 1;
}
else{
return 0;
}
}
}
