#include <bits/stdc++.h>
#include "supertrees.h"
using namespace std;
#define ll long long
#define endl "\n"
#define INF 1000000000
#define LINF 10000000000000000000LL
#define pb push_back
#define all(x) x.begin(), x.end()
#define len(s) (int)s.size()
#define test_case { int t; cin>>t; while(t--)solve(); }
#define single_case solve();
#define line cerr<<"----------"<<endl;
#define ios { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cerr.tie(NULL); }
#define mod 1000000007LL
const int N = 1005;
int parent[N], s[N];
int find_parent(int u)
{
while(parent[u]!=u)
{
parent[u] = parent[parent[u]];
u = parent[u];
}
return u;
}
void dsu(int u, int v)
{
u = find_parent(u);
v = find_parent(v);
if(u!=v)
{
if(s[u]<s[v]) swap(u, v);
s[u] += s[v];
parent[v] = u;
}
}
int construct(vector<vector<int> > p)
{
int n = len(p);
for(int i = 0;i<n;i++) parent[i] = i, s[i] = 1;
for(int i = 0;i<n;i++)
for(int j = 0;j<n;j++) if(p[i][j]==3||p[i][i]!=1) return 0;
for(int i = 0;i<n;i++)
for(int j = 0;j<n;j++) if(p[i][j]==1) dsu(i, j);
vector<int> r;
vector<int> rr(n, 0);
vector<vector<int> > res(n, vector<int>(n, 0));
for(int i = 0;i<n;++i) {
int x = find_parent(i);
if(x==i) r.pb(i), rr[i] = 1;
else res[i][x] = res[x][i] = 1;
}
for(int i = 0;i<n;i++)
{
if(find_parent(i)==i)
{
vector<int> q;
for(int j = 0;j<n;j++) if(j!=i&&find_parent(i)==i) q.pb(j);
for(int x : q)
{
for(int y : q)
{
if(x!=y)
{
if(p[x][y]!=1) return 0;
}
}
}
}
}
for(int i = 0;i<n;i++) parent[i] = i, s[i] = 1;
for(int i = 0;i<n;++i)
for(int j = 0;j<n;j++)
if(rr[i]==1&&rr[j]==1&&p[i][j]==2) dsu(i, j);
for(int i = 0;i<n;++i){
int x = find_parent(i);
if(x==i&&rr[i])
{
if(s[i]<3) return 0;
vector<int> q;
for(int j = 0;j<n;j++)
if(find_parent(j)==i&&j!=i) q.pb(j);
q.pb(i);
int pret = x;
for(int x : q) res[x][pret] = res[pret][x] = 1, pret = x;
}
}
build(res);
return 1;
}
