Number of Drawings

Time limit2sMemory limit128 MB

Summary

Given T polylines defined by their points, count how many separate connected drawings form when polylines that touch or overlap are merged into one group.

Level: Medium7 of 10
Topics: Geometry, Union-find, Implementation, Math
Solved: No attempts yet

Problem

A polyline is a shape made by connecting several points in order with continuous line segments. The endpoint of one segment is the starting point of the next segment.

If two polylines share at least one point, they belong to the same drawing. A shared point may be a vertex, an intersection point on the segments, or any point in an overlapping segment.

Given T polylines, find the number of separate drawings.

Input

The first line contains the number of polylines T.

For each polyline, the first line contains N, the number of points in that polyline. The next N lines contain the point coordinates x y in order.

N may be 1. T is less than 1000, and N is less than 500. Every coordinate is an integer from 0 to 10000, inclusive.

Output

Print the number of drawings on the first line.

Examples8

Example 1
Input
```
2
2
0 0
10 5
4
5 0
15 5
10 10
5 5
```
Expected output
```
2
```
Example 2
Input
```
2
2
0 0
10 10
2
0 10
10 0
```
Expected output
```
1
```
Example 3
Input
```
2
2
13 0
5 5
2
4 0
4 20
```
Expected output
```
2
```

Example 4

Input

Expected output

Example 5
Input
```
2
3
0 0
10 0
0 0
3
20 0
8 0
20 0
```
Expected output
```
1
```
Example 6
Input
```
5
1
1 1
1
2 2
1
3 3
1
4 4
2
3 3
4 4
```
Expected output
```
3
```
Example 7
Input
```
2
1
1 1
1
1 1
```
Expected output
```
1
```

Example 8

Input

Expected output