19680번 - Roads 서브태스크스페셜 저지다국어

문제

The government of Treeland wants to build a new road network. There are 2N cities in Treeland. The unfinished plan of the road network already contains N road segments, each of which connects two cities with a straight line. No two road segments have a common point (including their endpoints).

Your task is to determine N − 1 additional road segments satisfying the following conditions:

1. Every new road segment must connect two cities with a straight line.
2. If two segments (new or old) have a common point, then this point must be an endpoint of both segments.
3. The road network connects all cities: for each pair of cities there is a path consisting of segments that connects the two cities.

입력

The first line contains N, the number of existing road segments. Each of the following N lines contains four integers: x₁, y₁, x₂, y₂, where (x₁, y₁) and (x₂, y₂) are the coordinates of the endpoints of the segment.

출력

You should print N − 1 lines, each of them containing four integers, x₁, y₁, x₂, y₂, where (x₁, y₁) and (x₂, y₂) are the coordinates of the cities that are the endpoints of a new road segment. If there are multiple solutions, your program may output any of them.

제한

• 2 ≤ N ≤ 10⁵
• −10⁷ ≤ x_i, y_i ≤ 10⁷

서브태스크

힌트