```#include <bits/stdtr1c++.h>

using namespace std;
typedef long long ll;
typedef long double ld;
typedef complex<ld> pt;
typedef vector<pt> pol;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<ld> vd;
typedef vector<vd> vvd;
typedef pair<ll, ll> pii;
typedef vector<pii> vpii;
#define pb push_back
ld INF = 1e100;

ld EPS = 1e-8;
ld cp(const pt &a, const pt &b) { return imag(conj(a)*b); }
ld dp(const pt &a, const pt &b) { return real(conj(a)*b); }

inline ld sgn(const ld& x) { return abs(x) < EPS ? 0 : x/abs(x); }
inline bool cmp_lex(const pt& a, const pt& b)
{ return a.real() < b.real() || (a.real() == b.real() && a.imag() < b.imag()); }
inline bool cmp_lex_i(const pt &a, const pt &b)
{ return a.imag() < b.imag() || (a.imag() == b.imag() && a.real() < b.real()); }
// Does NOT include points on the ends of the segment.
inline bool on_segment(const pt &a, const pt &b, const pt &p) {
return abs(cp(b-a, p-a)) < EPS && dp(b-a, p-a) > 0 && dp(a-b, p-b) > 0; }

// Checks if p lies on the boundary of a polygon v.
inline bool on_boundary(const pol &v, const pt &p) { bool res = false;
for(auto i=v.size()-1,j=0ul;j<v.size();i=j++) res |= on_segment(v[i], v[j], p);
return res; }
// orientation does not matter !!!
bool pt_in_polygon(const pt &p, const pol &v){ if(on_boundary(v,p)) return true;
ld res = 0; for(auto i = v.size() - 1, j = 0ul; j < v.size(); i = j++)
res += atan2(cp(v[i] - p, v[j] - p), dp(v[i] - p, v[j] - p));
return abs(res) > 1; } // will be either 2*PI or 0
//! checks if p1 is inside p2
bool inside(vector<pt> &pts, vector<pt> &pts2) {
for (int i = 0; i < pts.size(); i++) {
if (pt_in_polygon(pts[i], pts2)) return true;
}
return false;
}
// handles ALL cases, change occurences of <= to < to exclude endpoints
bool seg_x_seg(pt a1, pt a2, pt b1, pt b2) {
//if (a1==a2 || b1==b2) return false; // uncomment to exclude endpoints
int s1 = sgn(cp(a2 - a1, b1 - a1)), s2 = sgn(cp(a2 - a1, b2 - a1));
int s3 = sgn(cp(b2 - b1, a1 - b1)), s4 = sgn(cp(b2 - b1, a2 - b1));
if(!s1 && !s2 && !s3) { // collinear
if (cmp_lex(a2, a1)) swap(a1, a2); if (cmp_lex(b2, b1)) swap(b1, b2);
//return cmp_lex(a1, b2) && cmp_lex(b1, a2);//uncomment to exclude endpoints
return !cmp_lex(b2, a1) && !cmp_lex(a2, b1);
} return s1*s2 <= 0 && s3*s4 <= 0; }
bool eq(ld a, ld b) {
return abs(a-b) < EPS;
}
bool ishoriz(pt a, pt b) {
return eq(a.imag(), b.imag());
}
bool bad_seg_x(pt i1, pt i2, pt j1, pt j2) {
bool h1 = ishoriz(i1, i2);
bool h2 = ishoriz(j1, j2);
if (h1 == h2) {
ld a, b, c, d;
ld e, f;
if (h1) {
a = min(i1.real(), i2.real());
b = max(i1.real(), i2.real());
c = min(j1.real(), j2.real());
d = max(j1.real(), j2.real());
e = i1.imag(); f = j1.imag();
} else {
a = min(i1.imag(), i2.imag());
b = max(i1.imag(), i2.imag());
c = min(j1.imag(), j2.imag());
d = max(j1.imag(), j2.imag());
e = i1.real(); f = j1.real();
}
if (!eq(e, f)) return false;
if (b-EPS < c || a > d-EPS) return false;
return true;
}
return false;
}
bool valid(vector<pt> &pts) {
int np = pts.size();
if (np <= 2) return false;
for (int i = 0; i < np; i++) {
int i2 = (i+np-1)%np;
for (int j = 0; j < np; j++) {
if (i == j) continue;
int j2 = (j+np-1) % np;
if (j2 == i || i2 == j) {
if (bad_seg_x(pts[i], pts[i2], pts[j], pts[j2])) {
return false;
}
continue;
}
if (seg_x_seg(pts[i], pts[i2], pts[j], pts[j2])) {
//cerr << i << " " << j << endl;
//cerr << pts[i] << " " << pts[i2] << " " << pts[j] << " " << pts[j2] << endl;
return false;
}
}
}
return true;
}
bool blah(vector<pt> &pts1, vector<pt> &pts2) {
int np1 = pts1.size();
int np2 = pts2.size();
for (int i = 0; i < np1; i++) {
int i2 = (i+np1-1) % np1;
for (int j = 0; j < np2; j++) {
int j2 = (j+np2-1) % np2;
if (seg_x_seg(pts1[i], pts1[i2], pts2[j], pts2[j2])) {
//cerr << i << " " << j << endl;
//cerr << pts1[i] << " " << pts1[i2] << " " << pts2[j] << " " << pts2[j2] << endl;
return true;
}
}
}
return false;
}
int main() {
int nc; cin >> nc;
for (int cs = 1; cs <= nc; cs++) {
int np; cin >> np;
vector<pt> polys[np];
for (int i = 0; i < np; i++) {
int npts; cin >> npts;
for (int j = 0; j < npts; j++) {
int x, y; cin >> x >> y;
if (j+1 != npts) {
polys[i].push_back(pt(x, y));
}
}
}
int indegree[np];
int depth[np];
int topo[np];
int ind = 0;
queue<int> q;
for (int i = 0; i < np; i++) {
if (!valid(polys[i])) {
cout << "INVALID POLYGON" << endl;
}
}
for (int i = 0; i < np; i++) {
for (int j = 0; j < i; j++) {
if (blah(polys[i], polys[j])) {
cout << "INTERSECTING POLYGONS" << endl;
}
if (inside(polys[i], polys[j])) {
//cerr << j << " " << i << endl;
}
if (inside(polys[j], polys[i])) {
//cerr << i << " " << j << endl;
}
}
}
memset(indegree, 0, sizeof indegree);
for (int i = 0; i < np; i++) {
for (int j = 0; j < adj[i].size(); j++) {
}
}
for (int i = 0; i < np; i++) {
if (indegree[i] == 0) {
q.push(i);
depth[i] = 0;
}
}
while (!q.empty()) {
int curr = q.front(); q.pop();
topo[ind] = curr;
ind++;
for (int i = 0; i < adj[curr].size(); i++) {
int j = adj[curr][i];
indegree[j]--;
if (indegree[j] == 0) {
q.push(j);
}
}
}
for (int i = 0; i < np; i++) {
int ii = topo[i];
for (int j = 0; j < adj[ii].size(); j++) {
}
}
for (int i = 0; i < np; i++) {
if (depth[i] > 1) {
cout << "INVALID NESTING" << endl;