#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
struct unionFind{
int par[1002];
void init(int n){
for(int i=0; i<n; i++) par[i] = i;
}
int find(int x){
if(x == par[x]) return x;
return par[x] = find(par[x]);
}
void merge(int x, int y){
x = find(x), y = find(y);
par[x] = y;
}
} uf1, uf2;
int n;
int mat[1002][1002];
vector<vector<int> > ans;
vector<int> degreeTwos[1002];
bool inCycle[1002];
int oneRoot[1002];
int construct(vector<vector<int>> _p){
int n = _p.size();
uf1.init(n);
uf2.init(n);
for(int i=0; i<n; i++) oneRoot[i] = -1;
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
mat[i][j] = _p[i][j];
if(mat[i][j] == 3) return 0;
if(mat[i][j] == 1) uf1.merge(i, j);
if(mat[i][j] == 1 || mat[i][j] == 2) uf2.merge(i, j);
}
}
ans.resize(n);
for(int i=0; i<n; i++) ans[i].resize(n);
/// 트리 만들기
for(int i=0; i<n; i++){
if(i != uf1.find(i)) continue;
for(int j=0; j<n; j++){
if(i == uf1.find(j) && j != i) ans[i][j] = ans[j][i] = 1;
}
degreeTwos[uf2.find(i)].push_back(i);
}
/// 사이클 만들기
for(int i=0; i<n; i++){
if(i != uf2.find(i) || (int)degreeTwos[i].size() <= 1) continue;
if((int)degreeTwos[i].size() == 2) return 0;
for(int j = 0; j < (int)degreeTwos[i].size() - 1; j++){
ans[degreeTwos[i][j]][degreeTwos[i][j+1]] = 1;
ans[degreeTwos[i][j+1]][degreeTwos[i][j]] = 1;
}
ans[degreeTwos[i].front()][degreeTwos[i].back()] = 1;
ans[degreeTwos[i].back()][degreeTwos[i].front()] = 1;
}
/// 올바른지 확인하기
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
if(uf1.find(i) == uf1.find(j)){
if(mat[i][j] != 1) return 0;
}
else if(uf2.find(i) == uf2.find(j)){
if(mat[i][j] != 2) return 0;
}
else{
if(mat[i][j] != 0) return 0;
}
}
}
build(ans);
return 1;
}
