cho.sh
Notes
Loading...

Line Segment Groups

Time limit

2s

Memory limit

128 MB

Problem

N line segments are given on a two-dimensional plane. Each segment is described by the x- and y-coordinates of its two endpoints.

Two segments belong to the same group if they meet. Meeting includes crossing in their interiors, touching at an endpoint, or an endpoint lying on the other segment.

Group membership is transitive: if segment A meets segment B and segment B meets segment C, then all three segments are in the same group even if A and C do not meet directly.

Find how many groups the given segments form and how many segments are in the largest group.

Input

The first line contains N (1 <= N <= 3,000), the number of line segments.

Each of the next N lines contains four integers x1 y1 x2 y2, the coordinates of the two endpoints of one segment. The absolute value of every coordinate is at most 5,000. Values on the same line are separated by spaces.

Output

Print the number of groups on the first line.

Print the number of segments in the largest group on the second line.