2 人解决，9 人已尝试。
6 份提交通过，共有 48 份提交。
9.6 EMB 奖励。
单点时限: 2.0 sec
内存限制: 256 MB
Antigravity has been widely used for a long time on the Olympia planet. The Olympian ministry of entertainment opened a new set of sightseeing platforms, that immovably hang at different heights above the Rio-ACM river. The platforms are small and may be considered as points. The river can be considered approximately straight, so all the platforms (points) are placed in a vertical plane. That is, the location of each platform can be described by two coordinates: x-coordinate specifies the horizontal distance from the river‘s source, y-coordinate – the height above the water. No platform is located exactly under any other one – thus, all x-coordinates are distinct.
Unfortunately, these platforms didn‘t prove to be popular for sightseeing, so the ministry is looking for a plan how to use them in another way – preferably such a way, which doesn‘t require moving of the platforms. One of the plans suggests equipping the platforms as stations for the hang gliders (also known as delta-planes). It‘s not interesting to use antigravity in sports, so hang gliders can fly from any platform to a platform of lower or equal height only. On religious grounds, Olympians never fly hang gliders in the direction opposite to the river flow.
According to marketing researches, the route will be popular if and only if it allows the greatest possible number of consecutive flights from one platform to another one, next one, and so on. The length of flights has no significant influence on route‘s popularity.
Your task is to write a program to find which of the platforms will belong to at least one of the popular routes.
The 1st line of the input contains the number of test cases T. In each test case, the first line contains the number of platforms N (1<N<123456), each of following N lines contains two non-negative integer numbers — x- and y-coordinates of the corresponding platform.
The program should write to standard output T two-lines groups — the answers for the corresponding test cases. The first line in each group should contain the number of flights in the popular routes and the total number of platforms that belong to any of the popular routes. The second line in the group should contain a list (in ascending order) of x-coordinates of these platforms. Numbers in each line should be separated by spaces.
2 2 2 3 4 5 5 11 4 44 5 22 2 33 3 55 1
0 0 2 4 11 22 33 55
2 人解决，9 人已尝试。
6 份提交通过，共有 48 份提交。
9.6 EMB 奖励。