#include <bits/stdc++.h>
#include "supertrees.h"
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define N 1005
#define PB push_back
#define sz(x) int(x.size())
#define P 31
#define F first
#define M ll(1e9 + 7)
#define S second
#define all(x) x.begin(), x.end()
#define endl '\n'
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("fast-math")
//#pragma GCC optimize("no-stack-protector")
using namespace std;
//using namespace __gnu_pbds;
typedef long long ll;
//typedef tree<int, null_type, less_equal <int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
ll mlt(ll a, ll b) {return (a * b) % M;}
ll sm(ll a, ll b) {return (a + b) % M;}
int rk[N], pr[N];
void make(int x) {pr[x] = x; rk[x] = 1;}
int fnd(int x) {if (pr[x] != x) pr[x] = fnd(pr[x]); return pr[x];}
void link(int a, int b)
{
if (rk[b] > rk[a]) swap(a, b);
rk[a] += rk[b];
pr[b] = a;
}
int construct(vector<vector<int> > p)
{
int n = sz(p);
vector<vector<int> > answer; answer.clear();
bool f = 1, fr = 1, ft = 1;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) {if (p[i][j] == 2 || p[i][j] == 3) fr = 0; if (p[i][j] != 1) f = 0; if (p[i][j] == 1 || p[i][j] == 3) ft = 0;}
if (f)
{
answer.resize(n);
for (int i = 0; i < n; i++)
answer[i].resize(n, 0);
for (int i = 1; i < n; i++) answer[0][i] = 1;
for (int i = 1; i < n; i++) answer[i][0] = 1;
build(answer);
return 1;
}
if (fr)
{
bool good = 1;
answer.resize(n);
for (int i = 0; i < n; i++)
answer[i].resize(n, 0);
for (int i = 0; i < n; i++) make(i);
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (p[i][j] == 1)
{
int a = fnd(i), b = fnd(j);
if (a != b) {answer[i][j] = answer[j][i] = 1; link(a, b);}
}
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if ((p[i][j] == 1 && fnd(i) != fnd(j)) || (p[i][j] == 0 && fnd(i) == fnd(j))) good = 0;
if (good) build(answer);
return good;
}
if (ft)
{
bool good = 1;
answer.resize(n);
for (int i = 0; i < n; i++)
answer[i].resize(n, 0);
for (int i = 0; i < n; i++) make(i);
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (p[i][j] == 2)
{
int a = fnd(i), b = fnd(j);
if (a != b) link(a, b);
}
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if ((p[i][j] == 2 && fnd(i) != fnd(j)) || (p[i][j] == 0 && fnd(i) == fnd(j))) good = 0;
if (!good) return 0;
set <int> se; se.clear();
for (int i = 0; i < n; i++)
{
int id = fnd(i);
if (se.find(id) != se.end()) continue;
se.insert(id);
vector <int> pr; pr.clear();
for (int j = 0; j < n; j++)
if (fnd(j) == id)
pr.PB(j);
if (sz(pr) == 1) continue;
for (int j = 0; j < sz(pr); j++)
{
int nxt = (j + 1) % sz(pr);
answer[pr[j]][pr[nxt]] = answer[pr[nxt]][pr[j]] = 1;
}
}
if (!good) return 0;
build(answer);
return 1;
}
return 0;
}
//int main()
//{
//// freopen("help.in", "r", stdin); freopen("help.out", "w", stdout);
//
// ios_base::sync_with_stdio(0); istream::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//}
