Contour Lines

Time limit1sMemory limit128 MB

Summary

Given sets of axis-parallel polygons, decide whether each set can be ordered so every polygon lies inside the next.

Level: Medium6 of 10
Topics: Geometry, Sorting, Implementation
Solved: No attempts yet

Problem

Consider a set of polygons whose sides are all parallel to the coordinate axes. Such a set is called a system of contour lines if all of its polygons can be ordered so that the first polygon contains the second one in its interior, the second polygon contains the third one in its interior, and so on. In other words, the polygons can be arranged as a strictly nested chain in which each polygon lies entirely inside the previous one.

Given several sets of axis-parallel polygons, decide for each set whether it is a system of contour lines.

Write a program that:

reads the descriptions of several sets of polygons,
for each set decides whether it is a system of contour lines,
writes the answers to standard output.

Input

The first line contains one integer $t$ ( $1 \le t \le 10$ ), the number of sets to process. The $t$ sets follow.

The first line of each set contains one integer $n$ ( $1 \le n \le 250$ ), the number of polygons in the set. Each of the next $n$ lines describes one polygon. Such a line begins with one integer $m_i$ ( $4 \le m_i \le 250$ ), the number of vertices of the $i$ -th polygon, followed by $m_i$ pairs of integers $x_{ij}$ and $y_{ij}$ ( $0 \le x_{ij}, y_{ij} \le 200\,000$ ) that give the coordinates of the consecutive vertices of the polygon, separated by single spaces.

Every polygon has sides parallel to the coordinate axes, no two adjacent sides are collinear, and the boundary of each polygon does not cross itself.

Output

Print $t$ lines. The $k$ -th line must contain the word TAK (meaning yes) if the $k$ -th set of polygons is a system of contour lines, and NIE (meaning no) otherwise.

Hint

Nested axis-parallel polygons forming contour lines

Examples4

Example 1

Input

3
3
6 1 1 5 1 5 4 4 4 4 6 1 6
6 0 0 0 7 5 7 5 5 7 5 7 0
4 2 3 3 3 3 4 2 4
3
4 2 2 3 2 3 3 2 3
8 1 1 1 4 3 4 3 6 5 6 5 4 4 4 4 1
4 0 0 6 0 6 5 0 5
3
6 1 1 5 1 5 4 4 4 4 6 1 6
6 0 0 0 7 5 7 5 5 7 5 7 0
4 2 3 4 3 4 4 2 4

Expected output

TAK
NIE
NIE

Example 2
Input
```
1
1
4 0 0 10 0 10 10 0 10
```
Expected output
```
TAK
```

Example 3

Input

1
2
4 0 0 10 0 10 10 0 10
4 2 2 8 2 8 8 2 8

Expected output

TAK

Example 4

Input

1
2
4 0 0 2 0 2 2 0 2
4 5 0 7 0 7 2 5 2

Expected output

NIE