Status:  Past  Start:  20141004 12:30:00  End:  20141004 16:30:00 
The 2014 ACMICPC Caribbean National Contests (Real contest)
Problem
2954  Marketland
Created by  Luis Manuel Díaz Barón 
Added by  luismo (20140612) 
Limits 
Total Time: 90000 MS

Test Time:
6000 MS
Memory: 62 MB  Output: 64 MB  Size:
14 KB

Enabled languages  
Available in 
Description
Marketland is the favorite place for the residents of Manhattan to go shopping. It consists of N markets, numbered from 1 to N. Each market is located at a grid point (X , Y) on the Cartesian plane. There exist many tunnels. Each one connects two different markets. A single tunnel can be traversed in both directions from one endpoint to the other. In any of these tunnels, there is no other exit but the endpoints, which are the markets it connects. The length of the tunnel is the Manhattan Distance between the markets it connects (were you expecting some other distance metric from the people of "Manhattan"?) . A route is formed by one or more tunnels and has two or more markets on it. Its length is the sum of the distances of its tunnels. There is exactly one route between any pair of markets.
Engineers are planning to increase the number of routes in Marketland. Sadly, they don't have enough money to build more than one tunnel. They receive S suggestions, each one consists of two integers F and G meaning that markets F and G wants to have a tunnel connecting each other. There will be no duplicate suggestions and no two suggestions will involve the same two markets. Among the suggestions, the engineers will choose the best one for the city: they will choose to build a tunnel between two markets such that there is a closed route (starting and ending at some market M) that maximizes the number of markets on it (without repeating any of them). If several routes have the same maximal number markets, the engineers will choose the one that minimizes its length. If there is more than one suggestion that satisfies the conditions above, you should count all of them.
Engineers are planning to increase the number of routes in Marketland. Sadly, they don't have enough money to build more than one tunnel. They receive S suggestions, each one consists of two integers F and G meaning that markets F and G wants to have a tunnel connecting each other. There will be no duplicate suggestions and no two suggestions will involve the same two markets. Among the suggestions, the engineers will choose the best one for the city: they will choose to build a tunnel between two markets such that there is a closed route (starting and ending at some market M) that maximizes the number of markets on it (without repeating any of them). If several routes have the same maximal number markets, the engineers will choose the one that minimizes its length. If there is more than one suggestion that satisfies the conditions above, you should count all of them.
Marketland is the favorite place for the residents of Manhattan to go shopping. It consists of N markets, numbered from 1 to N. Each market is located at a grid point (X , Y) on the Cartesian plane. There exist many tunnels. Each one connects two different markets. A single tunnel can be traversed in both directions from one endpoint to the other. In any of these tunnels, there is no other exit but the endpoints, which are the markets it connects. The length of the tunnel is the Manhattan Distance between the markets it connects (were you expecting some other distance metric from the people of "Manhattan"?) . A route is formed by one or more tunnels and has two or more markets on it. Its length is the sum of the distances of its tunnels. There is exactly one route between any pair of markets.
Engineers are planning to increase the number of routes in Marketland. Sadly, they don't have enough money to build more than one tunnel. They receive S suggestions, each one consists of two integers F and G meaning that markets F and G wants to have a tunnel connecting each other. There will be no duplicate suggestions and no two suggestions will involve the same two markets. Among the suggestions, the engineers will choose the best one for the city: they will choose to build a tunnel between two markets such that there is a closed route (starting and ending at some market M) that maximizes the number of markets on it (without repeating any of them). If several routes have the same maximal number markets, the engineers will choose the one that minimizes its length. If there is more than one suggestion that satisfies the conditions above, you should count all of them.
Engineers are planning to increase the number of routes in Marketland. Sadly, they don't have enough money to build more than one tunnel. They receive S suggestions, each one consists of two integers F and G meaning that markets F and G wants to have a tunnel connecting each other. There will be no duplicate suggestions and no two suggestions will involve the same two markets. Among the suggestions, the engineers will choose the best one for the city: they will choose to build a tunnel between two markets such that there is a closed route (starting and ending at some market M) that maximizes the number of markets on it (without repeating any of them). If several routes have the same maximal number markets, the engineers will choose the one that minimizes its length. If there is more than one suggestion that satisfies the conditions above, you should count all of them.
Marketland is the favorite place for the residents of Manhattan to go shopping. It consists of N markets, numbered from 1 to N. Each market is located at a grid point (X , Y) on the Cartesian plane. There exist many tunnels. Each one connects two different markets. A single tunnel can be traversed in both directions from one endpoint to the other. In any of these tunnels, there is no other exit but the endpoints, which are the markets it connects. The length of the tunnel is the Manhattan Distance between the markets it connects (were you expecting some other distance metric from the people of "Manhattan"?) . A route is formed by one or more tunnels and has two or more markets on it. Its length is the sum of the distances of its tunnels. There is exactly one route between any pair of markets.
Engineers are planning to increase the number of routes in Marketland. Sadly, they don't have enough money to build more than one tunnel. They receive S suggestions, each one consists of two integers F and G meaning that markets F and G wants to have a tunnel connecting each other. There will be no duplicate suggestions and no two suggestions will involve the same two markets. Among the suggestions, the engineers will choose the best one for the city: they will choose to build a tunnel between two markets such that there is a closed route (starting and ending at some market M) that maximizes the number of markets on it (without repeating any of them). If several routes have the same maximal number markets, the engineers will choose the one that minimizes its length. If there is more than one suggestion that satisfies the conditions above, you should count all of them.
Engineers are planning to increase the number of routes in Marketland. Sadly, they don't have enough money to build more than one tunnel. They receive S suggestions, each one consists of two integers F and G meaning that markets F and G wants to have a tunnel connecting each other. There will be no duplicate suggestions and no two suggestions will involve the same two markets. Among the suggestions, the engineers will choose the best one for the city: they will choose to build a tunnel between two markets such that there is a closed route (starting and ending at some market M) that maximizes the number of markets on it (without repeating any of them). If several routes have the same maximal number markets, the engineers will choose the one that minimizes its length. If there is more than one suggestion that satisfies the conditions above, you should count all of them.
Input specification
In the first line, there are two spaceseparated integer numbers: 2 <= N <= 10^5 (the number of markets) and 1 <= S <= 10^5 (the number of suggestions). The next N lines contain two spaceseparated integer numbers X and Y, (10^7 <= X, Y <= 10^7) denoting the coordinates of the ith market on the grid. N  1 lines follow, each containing two spaceseparated integers A and B, representing an existing tunnel between markets A and B. Finally, S lines follow, each containing two spaceseparated integer numbers 1 <= F <= N and 1 <= G <= N (F != G) representing a suggestion from markets F and G to build a tunnel to connect them.
In the first line, there are two spaceseparated integer numbers: 2 <= N <= 10^5 (the number of markets) and 1 <= S <= 10^5 (the number of suggestions). The next N lines contain two spaceseparated integer numbers X and Y, (10^7 <= X, Y <= 10^7) denoting the coordinates of the ith market on the grid. N  1 lines follow, each containing two spaceseparated integers A and B, representing an existing tunnel between markets A and B. Finally, S lines follow, each containing two spaceseparated integer numbers 1 <= F <= N and 1 <= G <= N (F != G) representing a suggestion from markets F and G to build a tunnel to connect them.
In the first line, there are two spaceseparated integer numbers: 2 <= N <= 10^5 (the number of markets) and 1 <= S <= 10^5 (the number of suggestions). The next N lines contain two spaceseparated integer numbers X and Y, (10^7 <= X, Y <= 10^7) denoting the coordinates of the ith market on the grid. N  1 lines follow, each containing two spaceseparated integers A and B, representing an existing tunnel between markets A and B. Finally, S lines follow, each containing two spaceseparated integer numbers 1 <= F <= N and 1 <= G <= N (F != G) representing a suggestion from markets F and G to build a tunnel to connect them.
Output specification
Output three lines:
 On the first line, print the string "Markets: ", without quotes, followed by the number of markets on an optimal closed route.
 On the second line, print the string "Route Lenght: ", without quotes, followed by the length of an optimal closed route.
 On the third line, print the string "Number of optimal suggestions: ", without quotes, followed by the number of suggestions that have an optimal closed route.
Output three lines:
 On the first line, print the string "Markets: ", without quotes, followed by the number of markets on an optimal closed route.
 On the second line, print the string "Route Lenght: ", without quotes, followed by the length of an optimal closed route.
 On the third line, print the string "Number of optimal suggestions: ", without quotes, followed by the number of suggestions that have an optimal closed route.
In the first line, there are two spaceseparated integer numbers: 2 <= N <= 10^5 (the number of markets) and 1 <= S <= 10^5 (the number of suggestions). The next N lines contain two spaceseparated integer numbers X and Y, (10^7 <= X, Y <= 10^7) denoting the coordinates of the ith market on the grid. N  1 lines follow, each containing two spaceseparated integers A and B, representing an existing tunnel between markets A and B. Finally, S lines follow, each containing two spaceseparated integer numbers 1 <= F <= N and 1 <= G <= N (F != G) representing a suggestion from markets F and G to build a tunnel to connect them.
Sample input
7 3
4 6
5 5
6 2
3 1
4 3
2 3
1 5
1 2
2 3
1 5
5 4
1 6
6 7
4 3
1 3
7 4
Sample output
Markets: 5Route Lenght: 16
Number of optimal suggestions: 1