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