Platforms#701
Antigravity has long been widely used on the Olympia planet. The Olympian Ministry of Entertainment has installed multiple sightseeing platforms that hang motionless at different heights above the Rio-ACM river. The platforms are small and may be considered as points. The river may be regarded as a straight line; thus, all platforms (points) are located in the same vertical plane. The location of each platform can be specified by two coordinates: -coordinate is the horizontal distance from the river's source, -coordinate is the height above the water. No platform is located exactly above another one, so all -coordinates are distinct.
Unfortunately, these platforms were not a great success, so the ministry is seeking alternative uses—preferably ones that do not require moving the platforms. One plan is to use them as stations for hang gliders (delta-planes). Since using antigravity in sport is not interesting, hang gliders can only fly from one platform to another platform at lower or equal height. For religious reasons, hang gliders never fly against the direction of the river's flow.
According to marketing calculations, a route is called popular if and only if it allows the maximum possible number of consecutive flights from platform to platform. The lengths of the flights do not influence the popularity of a route.
Your task is to determine which platforms will belong to at least one popular route.
The first line contains the number of test cases . The first line of each test case contains the number of platforms (1 < N < 123456). Each of the next lines contains two non-negative integers — the - and -coordinates of the corresponding platform.
Print answer groups, each consisting of two lines (for each test case). The first line of each group should contain the number of flights in any popular route and the total number of platforms that belong to any popular route. The second line in each group should contain a list (in ascending order) of the -coordinates of these platforms. Numbers in each line should be separated by spaces.
Example 1