2954 - Marketland

Created by Luis Manuel Díaz Barón
Added by luismo (2014-06-12)
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.
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.
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.

Input specification

In the first line, there are two space-separated 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 space-separated integer numbers X and Y, (-10^7 <= |X|, |Y| <= 10^7) denoting the coordinates of the i-th market on the grid. N - 1 lines follow, each containing two space-separated integers A and B, representing an existing tunnel between markets A and B. Finally, S lines follow, each containing two space-separated 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 space-separated 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 space-separated integer numbers X and Y, (-10^7 <= |X|, |Y| <= 10^7) denoting the coordinates of the i-th market on the grid. N - 1 lines follow, each containing two space-separated integers A and B, representing an existing tunnel between markets A and B. Finally, S lines follow, each containing two space-separated 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 space-separated 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 space-separated integer numbers X and Y, (-10^7 <= |X|, |Y| <= 10^7) denoting the coordinates of the i-th market on the grid. N - 1 lines follow, each containing two space-separated integers A and B, representing an existing tunnel between markets A and B. Finally, S lines follow, each containing two space-separated 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 space-separated 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 space-separated integer numbers X and Y, (-10^7 <= |X|, |Y| <= 10^7) denoting the coordinates of the i-th market on the grid. N - 1 lines follow, each containing two space-separated integers A and B, representing an existing tunnel between markets A and B. Finally, S lines follow, each containing two space-separated 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: 5
Route Lenght: 16
Number of optimal suggestions: 1

Hint(s)