시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB0000.000%

문제

Let us consider a set of polygons with sides parallel to the axes of the coordinate system. Such a set of polygons is called a system of contour lines, if it is possible to order all the polygons of the set, so that the first polygon contains the second polygon in its interior, the second polygon contains the third polygon in its interior etc.

Your task is to check, if a given set of polygons is a system of contour lines.

Write a program, which:

  • reads descriptions of a few sets of polygons,
  • for each set decides, if it is a system of contour lines,
  • writes the result to the standard output.

입력

In the first line there is one natural number t (1 ≤ t ≤ 10), denoting the number of sets to processed. Following, there are t data sets. The first line of each data set contains one integer n (1 ≤ n ≤ 250), denoting the number of polygons in this set. Each of the next n lines contains one integer mi (4 ≤ mi ≤ 250, 1 ≤ in), denoting the number of vertices of the i-th polygon, followed by mi pairs of integers xij and yij (0 ≤ xij, yij ≤ 200 000), separated with a single space. These pairs describe coordinates of consecutive vertices of the polygon. The sides of each polygon are parallel to the axes of the coordinate system. Furthermore, no two adjacent sides of any polygon are collinear. The perimeter of any polygon does not contain self-crossings.

출력

The standard output should contain t lines. The k-th line should contain one word TAK (i.e. yes in Polish), if the k-th set of polygons is a system of contour lines, NIE (i.e. no in Polish) otherwise.

예제 입력 1

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

예제 출력 1

TAK
NIE
NIE

힌트